oj.uz

Submission #147975

# Submission time Handle Problem Language Result Execution time Memory
147975 2019-08-31T10:23:55 Z MvC Necklace (Subtask 1-3) (BOI19_necklace1) C++11
25 / 85
 1481 ms 504 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.475)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 376 KB Output is correct
2 Correct 8 ms 376 KB Output is correct
3 Correct 173 ms 376 KB Output is correct
4 Correct 248 ms 504 KB Output is correct
5 Correct 430 ms 376 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 376 KB Output is correct
2 Correct 8 ms 376 KB Output is correct
3 Correct 173 ms 376 KB Output is correct
4 Correct 248 ms 504 KB Output is correct
5 Correct 430 ms 376 KB Output is correct
6 Correct 841 ms 404 KB Output is correct
7 Partially correct 1477 ms 404 KB Output is partially correct
8 Partially correct 1479 ms 396 KB Output is partially correct
9 Partially correct 1479 ms 392 KB Output is partially correct
10 Partially correct 1480 ms 396 KB Output is partially correct
11 Incorrect 1481 ms 412 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 376 KB Output is correct
2 Correct 8 ms 376 KB Output is correct
3 Correct 173 ms 376 KB Output is correct
4 Correct 248 ms 504 KB Output is correct
5 Correct 430 ms 376 KB Output is correct
6 Correct 841 ms 404 KB Output is correct
7 Partially correct 1477 ms 404 KB Output is partially correct
8 Partially correct 1479 ms 396 KB Output is partially correct
9 Partially correct 1479 ms 392 KB Output is partially correct
10 Partially correct 1480 ms 396 KB Output is partially correct
11 Incorrect 1481 ms 412 KB Output isn't correct
12 Halted 0 ms 0 KB -