oj.uz

Submission #147978

# Submission time Handle Problem Language Result Execution time Memory
147978 2019-08-31T10:26:44 Z MvC Necklace (Subtask 1-3) (BOI19_necklace1) C++11
25 / 85
 1500 ms 540 KB 
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
//#include "boxes.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<61);
const int inf=(1<<30);
const int nmax=1e4+50;
const int mod=1e9+7;
using namespace std;
string s,t,s1,t1,st;
int n,m,i,j,k,p,q,z[nmax];
pair<int,pair<int,int> >rs;
vector<int>rad,px,py;
bool zt(string ss,int x) 
{
    int sz=ss.length();
    z[0]=0;
    for(int i=1,l=0,r=0;i<sz;i++) 
    {
		z[i]=0;
        if(i<=r)z[i]=min(r-i+1,z[i-l]);
        while(i+z[i]<sz && ss[z[i]]==ss[i+z[i]])z[i]++;
        if(i+z[i]-1>r)l=i,r=i+z[i]-1;
        if(i>=x && z[i]==x)return 1;
    }
    return 0;
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>s>>t;
	n=s.size(),m=t.size();
	for(i=1;i<=min(n,m);i++)rad.pb(i);
	shuffle(rad.begin(),rad.end(),rng);
	for(k=0;k<min(n,m);k++)
	{
		px.clear(),py.clear();
		for(i=0;i<n-rad[k]+1;i++)px.pb(i);
		for(i=0;i<m-rad[k]+1;i++)py.pb(i);
		shuffle(px.begin(),px.end(),rng);
		shuffle(py.begin(),py.end(),rng);
		for(i=0;i<n-rad[k]+1;i++)
		{
			if((double)clock()/CLOCKS_PER_SEC>=1.495)break;
			if(rs.fr>=rad[k])break;
			for(j=0;j<m-rad[k]+1;j++)
			{
				s1=t1="";
				for(p=px[i],q=py[j];p<px[i]+rad[k];p++,q++)
				{
					s1+=s[p];
					t1+=t[q];
				}
				st=s1+'#'+t1+t1;
				if(zt(st,rad[k]))
				{
					rs=max(rs,mkp(rad[k],mkp(px[i],py[j])));
					break;
				}
				reverse(t1.begin(),t1.end());
				st=s1+'#'+t1+t1;
				if(zt(st,rad[k]))
				{
					rs=max(rs,mkp(rad[k],mkp(px[i],py[j])));
					break;
				}
			}
		}
	}
	cout<<rs.fr<<endl<<rs.sc.fr<<" "<<rs.sc.sc<<endl;
	return 0;
}

Compilation message

necklace.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
necklace.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 504 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 166 ms 376 KB Output is correct
4 Correct 264 ms 504 KB Output is correct
5 Correct 432 ms 388 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 504 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 166 ms 376 KB Output is correct
4 Correct 264 ms 504 KB Output is correct
5 Correct 432 ms 388 KB Output is correct
6 Correct 817 ms 408 KB Output is correct
7 Partially correct 1497 ms 540 KB Output is partially correct
8 Partially correct 1499 ms 520 KB Output is partially correct
9 Execution timed out 1501 ms 504 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 504 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 166 ms 376 KB Output is correct
4 Correct 264 ms 504 KB Output is correct
5 Correct 432 ms 388 KB Output is correct
6 Correct 817 ms 408 KB Output is correct
7 Partially correct 1497 ms 540 KB Output is partially correct
8 Partially correct 1499 ms 520 KB Output is partially correct
9 Execution timed out 1501 ms 504 KB Time limit exceeded
10 Halted 0 ms 0 KB -