Submission #383304

#	Time	Username	Problem	Language	Result	Execution time	Memory
383304		drekavac	Ispit (COCI19_ispit)	C++14	90 / 90	1783 ms	4612 KiB

Main

#include <bits/stdc++.h>
#define ll long long int
using namespace std;
#define ll long long int

int NM = 600, p = 31, n, k;
ll m = (ll)1<<55;

string s;
vector< vector< pair<ll, ll>> > v(NM);
vector<int> ppow(NM, 1);



int get(char c){
	return c-'a';
}

void hashF(int red){
	for(int i=0; i+k <= n; i++){
		vector<int> kv;
		vector<int> ost;
		
		for(int j=0; j<k; j++)
			kv.push_back(get(s[i+j]));
			
		sort(kv.begin(), kv.end());
			
			
		ll ret = 0, ret2 = 0;
		
		for(int j=0; j<k; j++){
			ret += kv[j]*ppow[j];
			ret = ret % m;
		}
	
	
		for(int j=0; j<i; j++)
			ost.push_back(get(s[j]));
		for(int j=i+k; j<n; j++)
			ost.push_back(get(s[j]));
	
		for(int j=0; j<n-k; j++){
			ret2 += ost[j]*ppow[j];
			ret2 = ret2 % m;
		}
	
		v[red].push_back(make_pair(ret, ret2));
	}
}


int main(){
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	
	cin >> n >> k;
	
	for(int i=1; i<k+2; i++) ppow[i] = (p*ppow[i-1])%m;

	for(int i=0; i<n; i++){
		cin>>s;	
		
		hashF(i);
	}	
	

	int d = v[0].size(); 
	
	
	for(int i=0; i<d; i++){//biramo kolone
		
		for(int a=0; a<n; a++)
			for(int b=a+1; b<n; b++)
				if(v[a][i]==v[b][i]){
					cout<<"DA";
					return 0;
				}
		
	}
	
	cout<<"NE";
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9