oj.uz

Submission #147963

# Submission time Handle Problem Language Result Execution time Memory
147963 2019-08-31T10:16:52 Z MvC Necklace (Subtask 1-3) (BOI19_necklace1) C++11
25 / 85
 1481 ms 508 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.480)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 12 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 184 ms 428 KB Output is correct
4 Correct 267 ms 376 KB Output is correct
5 Correct 437 ms 424 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 3 ms 376 KB Output is correct
3 Correct 184 ms 428 KB Output is correct
4 Correct 267 ms 376 KB Output is correct
5 Correct 437 ms 424 KB Output is correct
6 Correct 795 ms 508 KB Output is correct
7 Partially correct 1480 ms 420 KB Output is partially correct
8 Partially correct 1480 ms 504 KB Output is partially correct
9 Partially correct 1480 ms 396 KB Output is partially correct
10 Partially correct 1481 ms 504 KB Output is partially correct
11 Incorrect 1480 ms 408 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 3 ms 376 KB Output is correct
3 Correct 184 ms 428 KB Output is correct
4 Correct 267 ms 376 KB Output is correct
5 Correct 437 ms 424 KB Output is correct
6 Correct 795 ms 508 KB Output is correct
7 Partially correct 1480 ms 420 KB Output is partially correct
8 Partially correct 1480 ms 504 KB Output is partially correct
9 Partially correct 1480 ms 396 KB Output is partially correct
10 Partially correct 1481 ms 504 KB Output is partially correct
11 Incorrect 1480 ms 408 KB Output isn't correct
12 Halted 0 ms 0 KB -