oj.uz

Submission #96577

# Submission time Handle Problem Language Result Execution time Memory
96577 2019-02-10T10:51:24 Z mraron Ispit (COCI19_ispit) C++14
90 / 90
 123 ms 34088 KB 
/*
ID: noszaly1
TASK: {TASK}
LANG: C++11               
*/

//Noszály Áron 11o Debreceni Fazekas Mihály Gimnázium

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair

#ifndef ONLINE_JUDGE
#  define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
#  define LOG(x) ((void)0)
#endif

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const double PI=acos(-1);

template<typename T> T getint() {
	T val=0;
	char c;
	
	bool neg=false;
	while((c=gc()) && !(c>='0' && c<='9')) {
		neg|=c=='-';
	}

	do {
		val=(val*10)+c-'0';
	} while((c=gc()) && (c>='0' && c<='9'));

	return val*(neg?-1:1);
}

struct rolling_hash { 
	vector<ll> lst;
	vector<ll> hatv;
	
	ll p;
	ll mod; 

	rolling_hash(string& t, ll p_, ll mod_) {
		lst.resize(sz(t));
		hatv.resize(sz(t));
		
		p=p_;
		mod=mod_;
		
		ll curr=p;
		
		lst[0]=t[0]%mod;
		hatv[0]=1;
		for(int i=1;i<sz(t);++i) {
			lst[i]=(lst[i-1]+curr*t[i])%mod;
			hatv[i]=curr;
			curr=(curr*p)%mod;
		}
	}
	
	ll base_hash_fast(ll l, ll r) { 
		ll hsh=(lst[r]-(l>0?lst[l-1]:0)+mod); //ez most p^l-es, tehát sz(lst)-l-1-el kell megszoroznunk
		return (hsh*hatv[sz(lst)-l-1])%mod;
	}
	
	bool probably_equal(ll l1, ll r1, ll l2, ll r2) {				
		if(r1-l1!=r2-l2) return false;

		if(l1>l2) {
			swap(l1, l2);
			swap(r1, r2);
		}
				
		ll egyik=(lst[r2]-(l2>0?lst[l2-1]:0)+mod), masik=(lst[r1]-(l1>0?lst[l1-1]:0)+mod);
		return (egyik-(masik*hatv[l2-l1]))%mod==0; //WATCH OUT FOR THIS KIND OF ERROR!!
	}
};

ll p1=19, mod1=1e9+7;
ll p2=31, mod2=1000000409;
int n,k;

string t[501];
int szum[501][501][26];

int main() {
	IO;
	cin>>n>>k;
	vector<rolling_hash> hsh1, hsh2;
	for(int i=0;i<n;++i) {
		cin>>t[i];
		hsh1.push_back(rolling_hash(t[i], p1, mod1));
		hsh2.push_back(rolling_hash(t[i], p2, mod2));
	}
	
	for(int i=0;i<n;++i) {
		for(int j=0;j<n;++j) {
			szum[i][j][t[i][j]-'a']++;
			if(j>0) {
				for(int k=0;k<26;++k) {
					szum[i][j][k]+=szum[i][j-1][k];
				}
			}
		}
	}

	bool ans=false;
	for(int i=0;i<n&&!ans;++i) {
		for(int j=i+1;j<n&&!ans;++j) {
			//bináris keresés, hogy meddig egyenlőek
			int L=-1, R=n;
			
			if(t[i][0]==t[j][0]) {
				L++;
				for(int k=10;k>=0;k--) {
					int akt=L+(1<<k);
					if(akt<n) {
						if(hsh1[i].base_hash_fast(0,akt)==hsh1[j].base_hash_fast(0,akt)&&
						   hsh2[i].base_hash_fast(0,akt)==hsh2[j].base_hash_fast(0,akt)){
							L=akt;
						}
					}
				}
			}

			if(t[i][n-1]==t[j][n-1]) {
				R--;
				for(int k=10;k>=0;k--) {
					int akt=R-(1<<k);
					if(akt>=0) {
						if(hsh1[i].base_hash_fast(akt,n-1)==hsh1[j].base_hash_fast(akt,n-1)&&
						   hsh2[i].base_hash_fast(akt,n-1)==hsh2[j].base_hash_fast(akt,n-1)){
							R=akt;
						}
					}
				}
			}
			
			if(R==0 && L==n-1) {
				ans=true;
				break ;
			}
			
			assert(L<R);
			
			bool ok=true;
			for(int l=0;ok&&l<26;++l) {
				ok&=(szum[i][R-1][l]-(L>=0?szum[i][L][l]:0))==(szum[j][R-1][l]-(L>=0?szum[j][L][l]:0));
			}
			
			if(ok && R-L-1<=k) ans|=true;
		}
	}
	
	cout<<(ans?"DA":"NE")<<"\n";
	return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6520 KB Output is correct
2 Correct 14 ms 6520 KB Output is correct
3 Correct 23 ms 6540 KB Output is correct
4 Correct 11 ms 6648 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6648 KB Output is correct
2 Correct 11 ms 6644 KB Output is correct
3 Correct 11 ms 6520 KB Output is correct
4 Correct 17 ms 6520 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6636 KB Output is correct
2 Correct 10 ms 6624 KB Output is correct
3 Correct 17 ms 6568 KB Output is correct
4 Correct 10 ms 6520 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6592 KB Output is correct
2 Correct 9 ms 6520 KB Output is correct
3 Correct 10 ms 6492 KB Output is correct
4 Correct 16 ms 6520 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 34040 KB Output is correct
2 Correct 55 ms 34040 KB Output is correct
3 Correct 95 ms 33956 KB Output is correct
4 Correct 62 ms 34076 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 34088 KB Output is correct
2 Correct 53 ms 33988 KB Output is correct
3 Correct 50 ms 34060 KB Output is correct
4 Correct 117 ms 34076 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 33996 KB Output is correct
2 Correct 45 ms 34012 KB Output is correct
3 Correct 123 ms 34012 KB Output is correct
4 Correct 52 ms 33956 KB Output is correct