oj.uz

Submission #1093203

# Submission time Handle Problem Language Result Execution time Memory
1093203 2024-09-26T08:57:28 Z concaccon Lozinke (COCI17_lozinke) C++17
0 / 100
 58 ms 64292 KB 
#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fol(i,a,b) for(int i=a;i>=b;i--)
#define base 31
#define ll long long
#define maxn 1000000
#define f first
#define s second
#define pb push_back
#define el cout << '\n'
#define pii pair<int,int>
const int inf=1e9+7;
const int mod=1e9+7;
using namespace std;
string inp[maxn];
int n;
namespace task1{
	int h[10][maxn],p[maxn];
	ll get(int i,int l,int r){
		return (h[i][r]-h[i][l-1]*p[(r-l+1)]%mod+mod)%mod;
	}
	void solve(){
		p[0]=1;
		fo(i,1,11) p[i]=p[i-1]*base%mod;
		fo(i,1,n) {
			int k=inp[i].size();
			string s=' '+inp[i];
			fo(j,1,k) h[i][j]=(h[i][j-1]*base+s[j]-'a'+1)%mod;
		}
		int res=0;
		fo(i,1,n){
			fo(j,1,n)if(i!=j && inp[i].size()<=inp[j].size()){
				fo(k,0,inp[j].size()-inp[i].size()+1) {
					//cout <<get(i,1,inp[i].size())<< ' '<<get(j,k+1,k+inp[i].size()),el;
					if(get(i,1,inp[i].size())==get(j,k+1,k+inp[i].size())){
						res++;
						break;
					}
				}
			}
		}
		cout <<res;
	}
}
namespace task2{
	int h[10][maxn],p[maxn];
	ll get(int i,int l,int r){
		return (h[i][r]-h[i][l-1]*p[(r-l+1)]%mod+mod)%mod;
	}
	void solve(){
		p[0]=1;
		fo(i,1,11) p[i]=p[i-1]*base%mod;
		fo(i,1,n) {
			int k=inp[i].size();
			string s=' '+inp[i];
			fo(j,1,k) h[i][j]=(h[i][j-1]*base+s[j]-'a'+1)%mod;
		}
		map<int,int > m;
		fo(i,1,n){
			fo(k,1,inp[i].size()){
				string s=' '+inp[i];
				map<int,int> ch;
				fo(j,1,inp[i].size()-k+1) if(ch[get(i,j,j+k-1)]==0) m[get(i,j,j+k-1)]++,ch[get(i,j,j+k-1)]++;
			}
		}
		int res=0;
		fo(i,1,n) res+=m[get(i,1,inp[i].size())]-1;
		cout <<res;
	}
}
signed main(){
	cin >> n;
	fo(i,1,n) cin >> inp[i];
	task2::solve();
}

Compilation message

lozinke.cpp: In function 'void task1::solve()':
lozinke.cpp:3:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define fo(i,a,b) for(int i=a;i<=b;i++)
......
   34 |     fo(k,0,inp[j].size()-inp[i].size()+1) {
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lozinke.cpp:34:5: note: in expansion of macro 'fo'
   34 |     fo(k,0,inp[j].size()-inp[i].size()+1) {
      |     ^~
lozinke.cpp: In function 'void task2::solve()':
lozinke.cpp:3:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define fo(i,a,b) for(int i=a;i<=b;i++)
......
   61 |    fo(k,1,inp[i].size()){
      |       ~~~~~~~~~~~~~~~~~         
lozinke.cpp:61:4: note: in expansion of macro 'fo'
   61 |    fo(k,1,inp[i].size()){
      |    ^~
lozinke.cpp:3:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define fo(i,a,b) for(int i=a;i<=b;i++)
......
   64 |     fo(j,1,inp[i].size()-k+1) if(ch[get(i,j,j+k-1)]==0) m[get(i,j,j+k-1)]++,ch[get(i,j,j+k-1)]++;
      |        ~~~~~~~~~~~~~~~~~~~~~    
lozinke.cpp:64:5: note: in expansion of macro 'fo'
   64 |     fo(j,1,inp[i].size()-k+1) if(ch[get(i,j,j+k-1)]==0) m[get(i,j,j+k-1)]++,ch[get(i,j,j+k-1)]++;
      |     ^~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 31836 KB Output isn't correct
2 Runtime error 47 ms 64152 KB Execution killed with signal 11
3 Runtime error 36 ms 64088 KB Execution killed with signal 11
4 Runtime error 41 ms 64088 KB Execution killed with signal 11
5 Runtime error 49 ms 64080 KB Execution killed with signal 11
6 Runtime error 40 ms 64116 KB Execution killed with signal 11
7 Runtime error 41 ms 64084 KB Execution killed with signal 11
8 Runtime error 43 ms 64080 KB Execution killed with signal 11
9 Runtime error 47 ms 64292 KB Execution killed with signal 11
10 Runtime error 40 ms 64080 KB Execution killed with signal 11
11 Runtime error 43 ms 64088 KB Execution killed with signal 11
12 Runtime error 47 ms 64084 KB Execution killed with signal 11
13 Runtime error 47 ms 64280 KB Execution killed with signal 11
14 Runtime error 46 ms 64084 KB Execution killed with signal 11
15 Runtime error 41 ms 64056 KB Execution killed with signal 11
16 Runtime error 58 ms 64084 KB Execution killed with signal 11
17 Runtime error 43 ms 64080 KB Execution killed with signal 11
18 Runtime error 42 ms 64080 KB Execution killed with signal 11
19 Runtime error 42 ms 64088 KB Execution killed with signal 11
20 Runtime error 38 ms 64240 KB Execution killed with signal 11