oj.uz

Submission #70147

# Submission time Handle Problem Language Result Execution time Memory
70147 2018-08-22T11:52:16 Z khohko popa (BOI18_popa) C++17
61 / 100
 303 ms 5424 KB 
#include <bits/stdc++.h>
#ifndef KHOKHO
#include "popa.h"
#endif // KHOKHO
#pragma GCC optimize("O3")
using namespace std;
#define ll int
#define pb push_back
#define fr first
#define sc second
#define MAX ((ll)(1e12+100))
#define MX ((ll)(1e6+100))
#define ARRS ((ll)(2e6+100))
#define HS ((ll)(233))
#define MOD ((ll)(1e9+7))
#define EP ((double)(1e-9))
#define LG 21
#define mul(a,b) a=((a)*(b))%MOD
using namespace std;

#ifdef KHOKHO
	ll aa[ARRS];
	ll qr=0;
	int query(int a, int b, int c, int d){
		ll x=0,y=0;
		qr++;
		for(int i=a; i<=b; i++)x=__gcd(x,aa[i]);
		for(int i=c; i<=d; i++)y=__gcd(y,aa[i]);
		return x==y;
	}
#endif
ll l[ARRS];
ll r[ARRS];

ll dp[1100][1100];
bitset<1100> ps[1100];
bitset<1100> psl[1100];
bitset<1100> tb;

ll bld(ll l,ll r,int *lt,int *rt){
	//slv(l,r);
	ll x=dp[l][r]-1;
	if(x==-2)return -1;
	if(x==-1)return -1;
	//cout<<l<<" "<<r<<" "<<x<<endl;
	lt[x]=bld(l,x,lt,rt);
	rt[x]=bld(x+1,r,lt,rt);
	return x;
}


int solve(int n, int* lt, int* rt){
	stack<ll> sk;
	for(int i=0; i<n; i++){
		while(sk.size()&&!query(sk.top(),i,sk.top(),sk.top())){
			r[sk.top()]=i-1;
			sk.pop();
		}
		sk.push(i);
	}

	while(sk.size())r[sk.top()]=n-1,sk.pop();
	for(int i=n-1; i>=0; i--){
		while(sk.size()&&!query(i,sk.top(),sk.top(),sk.top())){
			l[sk.top()]=i+1;
			sk.pop();
		}
		sk.push(i);
	}
	while(sk.size())l[sk.top()]=0,sk.pop();

//	for(int i=0; i<n; i++){
//		cout<<r[i]<<" ";
//	}
//	cout<<endl;
//	for(int i=0; i<n; i++){
//		cout<<l[i]<<" ";
//	}
//	cout<<endl;

	for(int i=0; i<=n; i++)ps[i].reset();
	for(int i=0; i<=n; i++)psl[i].reset();
	for(int i=0; i<=n; i++)
		for(int j=0; j<=n; j++)
			dp[i][j]=0;


	for(int d=0; d<=n; d++){
		for(int i=0; i<=n-d; i++){
			ll j=i+d;
			if(i==j){
				dp[i][j]=-1;
			}
			else {
				tb.reset();
				tb=ps[i]&psl[j];

				//cout<<"-->"<<endl;
				if(tb.any()){
					ll k=tb._Find_first();
					//cout<<"-->"<<k<<endl;
					dp[i][j]=k+1;
				}
				ll k=i;
				if(dp[i][k]&&dp[k+1][j]&&l[k]<=i&&j-1<=r[k])
					{dp[i][j]=k+1;}
				k=j-1;
				if(dp[i][k]&&dp[k+1][j]&&l[k]<=i&&j-1<=r[k])
					{dp[i][j]=k+1;}

			}
			//cout<<dp[i][j]<<" "<<i<<" "<<j<<endl;
			//cout<<ps[i]<<" "<<psl[j]<<endl;
			if(j<n&&dp[i][j]&&l[j]<=i){ps[i][j]=1;}
			if(i&&dp[i][j]&&r[i-1]>=j-1){psl[j][i-1]=1;}
		}
	}
	//slv(0,n);

	return bld(0,n,lt,rt);
}

#ifdef KHOKHO
int pa[ARRS];
int pb[ARRS];

int main(){
	#ifdef KHOKHO
		freopen("in.in","r",stdin);
		freopen("out.out","w",stdout);
	#endif // KHOKHO
	//ios::sync_with_stdio(0);

	ll n;
	cin>>n;
	for(int i=0; i<n; i++){
		cin>>aa[i];
	}
	ll rt=solve(n,pa,pb);
	cout<<rt<<endl;
	for(int i=0; i<n; i++){
		cout<<pa[i]<<" ";
	}
	cout<<endl;
	for(int i=0; i<n; i++){
		cout<<pb[i]<<" ";
	}
	cout<<endl;
	cout<<endl;
	cout<<"asked:"<<qr<<endl;

}
#endif

Subtask #1
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 760 KB Output is correct
2 Correct 19 ms 948 KB Output is correct
3 Correct 23 ms 948 KB Output is correct
4 Correct 20 ms 948 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 5312 KB Output is correct
2 Correct 292 ms 5424 KB Output is correct
3 Correct 163 ms 5424 KB Output is correct
4 Correct 290 ms 5424 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 5424 KB too many queries
2 Halted 0 ms 0 KB -