oj.uz

Submission #147972

# Submission time Handle Problem Language Result Execution time Memory
147972 2019-08-31T10:19:58 Z MvC Necklace (Subtask 1-3) (BOI19_necklace1) C++11
25 / 85
 1491 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;
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++)
	{
		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=i,q=j;p<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(i,j)));
					break;
				}
				reverse(t1.begin(),t1.end());
				st=s1+'#'+t1+t1;
				if(zt(st,rad[k]))
				{
					rs=max(rs,mkp(rad[k],mkp(i,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 13 ms 376 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 179 ms 388 KB Output is correct
4 Correct 285 ms 504 KB Output is correct
5 Correct 454 ms 476 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 376 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 179 ms 388 KB Output is correct
4 Correct 285 ms 504 KB Output is correct
5 Correct 454 ms 476 KB Output is correct
6 Correct 781 ms 504 KB Output is correct
7 Correct 1490 ms 504 KB Output is correct
8 Partially correct 1490 ms 480 KB Output is partially correct
9 Partially correct 1491 ms 476 KB Output is partially correct
10 Partially correct 1490 ms 480 KB Output is partially correct
11 Incorrect 1491 ms 504 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 13 ms 376 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 179 ms 388 KB Output is correct
4 Correct 285 ms 504 KB Output is correct
5 Correct 454 ms 476 KB Output is correct
6 Correct 781 ms 504 KB Output is correct
7 Correct 1490 ms 504 KB Output is correct
8 Partially correct 1490 ms 480 KB Output is partially correct
9 Partially correct 1491 ms 476 KB Output is partially correct
10 Partially correct 1490 ms 480 KB Output is partially correct
11 Incorrect 1491 ms 504 KB Output isn't correct
12 Halted 0 ms 0 KB -