Submission #1093202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093202		concaccon	Lozinke (COCI17_lozinke)	C++11	0 / 100	57 ms	64436 KiB

lozinke

#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];
	if(n<2000) task1::solve();
	else task2::solve();
}

Compilation message (stderr)

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