Submission #96577

#	Time	Username	Problem	Language	Result	Execution time	Memory
96577		mraron	Ispit (COCI19_ispit)	C++14	90 / 90	123 ms	34088 KiB

Main

/*
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 / 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