oj.uz

Submission #383304

# Submission time Handle Problem Language Result Execution time Memory
383304 2021-03-29T14:13:15 Z drekavac Ispit (COCI19_ispit) C++14
90 / 90
 1783 ms 4612 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 364 KB Output is correct
2 Correct 28 ms 492 KB Output is correct
3 Correct 121 ms 748 KB Output is correct
4 Correct 121 ms 748 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 364 KB Output is correct
2 Correct 26 ms 492 KB Output is correct
3 Correct 105 ms 876 KB Output is correct
4 Correct 102 ms 748 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 364 KB Output is correct
2 Correct 7 ms 364 KB Output is correct
3 Correct 79 ms 676 KB Output is correct
4 Correct 78 ms 620 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 364 KB Output is correct
2 Correct 18 ms 492 KB Output is correct
3 Correct 117 ms 748 KB Output is correct
4 Correct 116 ms 748 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 620 KB Output is correct
2 Correct 150 ms 876 KB Output is correct
3 Correct 517 ms 1132 KB Output is correct
4 Correct 517 ms 1232 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 620 KB Output is correct
2 Correct 33 ms 492 KB Output is correct
3 Correct 1783 ms 4468 KB Output is correct
4 Correct 1755 ms 4612 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 492 KB Output is correct
2 Correct 156 ms 748 KB Output is correct
3 Correct 1592 ms 2540 KB Output is correct
4 Correct 1572 ms 2612 KB Output is correct