oj.uz

Submission #68752

# Submission time Handle Problem Language Result Execution time Memory
68752 2018-08-18T10:26:36 Z istlemin popa (BOI18_popa) C++14
37 / 100
 617 ms 640 KB 
#include<bits/stdc++.h>
#include "popa.h"

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;
/*
ll Q = 0;
vi seq;

ll gcd(ll a,ll b){
	return b==0?a:gcd(b,a%b);
}

int query(int a,int b,int c,int d){
    ll gcd1 = seq[a];
    ll gcd2 = seq[c];
    rep(i,a,b+1) gcd1 = gcd(gcd1,seq[i]);
    rep(i,c,d+1) gcd2 = gcd(gcd2,seq[i]);
    ++Q;
    return gcd1==gcd2;
}
*/
vector<vector<bool> > same;
vi l;
vi r;
ll root;

ll findRoot(ll dn,ll up){
    rep(i,dn,up){
        bool allSame = true;
		rep(j,dn,up)
			if(!same[i][j]) allSame = false;
		if(allSame) return i;
    }
    return -1;
}

ll makeTree(ll dn,ll up){
    if(dn==up) return -1;
    ll ro = findRoot(dn,up);
    l[ro] = makeTree(dn,ro);
    r[ro] = makeTree(ro+1,up);
    return ro;
}

int solve(int n, int* Left, int* Right){
	l.assign(n,-1);
	r.assign(n,-1);
	same.assign(n,vector<bool>(n,true));

	rep(i,0,n)
	rep(j,0,n){
		if(i==j) continue;
        same[i][j] = query(i,i,min(i,j),max(i,j));
	}

    root = makeTree(0,n);

    rep(i,0,n){
		Left[i] = l[i];
		Right[i] = r[i];
    }
    return root;
}
/*
int main(){
	cin.sync_with_stdio(false);
	ll n; cin>>n;
	seq.resize(n);
    rep(i,0,n) cin>>seq[i];
    int left[n];
    int right[n];
    int root = solve(n,left,right);
    cout<<root<<endl;
    rep(i,0,n) cout<<left[i]<<" ";
    cout<<endl;
    rep(i,0,n) cout<<right[i]<<" ";
	cout<<endl;

	cout<<Q<<endl;
}*/

Subtask #1
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 248 KB Output is correct
2 Correct 617 ms 436 KB Output is correct
3 Correct 532 ms 436 KB Output is correct
4 Correct 603 ms 436 KB Output is correct

Subtask #2
0 / 24.0

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

Subtask #3
0 / 39.0

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