oj.uz

Submission #147976

# Submission time Handle Problem Language Result Execution time Memory
147976 2019-08-31T10:26:09 Z MvC Necklace (Subtask 1-3) (BOI19_necklace1) C++11
25 / 85
 1480 ms 532 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 12 ms 376 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 185 ms 476 KB Output is correct
4 Correct 250 ms 504 KB Output is correct
5 Correct 428 ms 504 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 376 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 185 ms 476 KB Output is correct
4 Correct 250 ms 504 KB Output is correct
5 Correct 428 ms 504 KB Output is correct
6 Correct 818 ms 504 KB Output is correct
7 Correct 1476 ms 532 KB Output is correct
8 Partially correct 1480 ms 516 KB Output is partially correct
9 Partially correct 1479 ms 404 KB Output is partially correct
10 Partially correct 1480 ms 512 KB Output is partially correct
11 Incorrect 1480 ms 396 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 12 ms 376 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 185 ms 476 KB Output is correct
4 Correct 250 ms 504 KB Output is correct
5 Correct 428 ms 504 KB Output is correct
6 Correct 818 ms 504 KB Output is correct
7 Correct 1476 ms 532 KB Output is correct
8 Partially correct 1480 ms 516 KB Output is partially correct
9 Partially correct 1479 ms 404 KB Output is partially correct
10 Partially correct 1480 ms 512 KB Output is partially correct
11 Incorrect 1480 ms 396 KB Output isn't correct
12 Halted 0 ms 0 KB -