oj.uz

Submission #147984

# Submission time Handle Problem Language Result Execution time Memory
147984 2019-08-31T10:30:39 Z MvC Necklace (Subtask 1-3) (BOI19_necklace1) C++11
25 / 85
 1495 ms 524 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++)
	{
		if(rs.fr>rad[k])continue;
		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.490)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 5 ms 376 KB Output is correct
3 Correct 181 ms 388 KB Output is correct
4 Correct 246 ms 392 KB Output is correct
5 Correct 434 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 5 ms 376 KB Output is correct
3 Correct 181 ms 388 KB Output is correct
4 Correct 246 ms 392 KB Output is correct
5 Correct 434 ms 376 KB Output is correct
6 Correct 761 ms 404 KB Output is correct
7 Correct 1490 ms 504 KB Output is correct
8 Partially correct 1493 ms 524 KB Output is partially correct
9 Partially correct 1495 ms 404 KB Output is partially correct
10 Partially correct 1494 ms 396 KB Output is partially correct
11 Incorrect 1495 ms 520 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 5 ms 376 KB Output is correct
3 Correct 181 ms 388 KB Output is correct
4 Correct 246 ms 392 KB Output is correct
5 Correct 434 ms 376 KB Output is correct
6 Correct 761 ms 404 KB Output is correct
7 Correct 1490 ms 504 KB Output is correct
8 Partially correct 1493 ms 524 KB Output is partially correct
9 Partially correct 1495 ms 404 KB Output is partially correct
10 Partially correct 1494 ms 396 KB Output is partially correct
11 Incorrect 1495 ms 520 KB Output isn't correct
12 Halted 0 ms 0 KB -