Submission #68759

#	Time	Username	Problem	Language	Result	Execution time	Memory
68759		istlemin	popa (BOI18_popa)	C++14	37 / 100	276 ms	2168 KiB

popa

#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;
}
*/

map<tuple<ll,ll,ll,ll>,bool> mem;

int makeQuery(ll a,ll b,ll c,ll d){
    tuple<ll,ll,ll,ll> queTup = make_tuple(a,b,c,d);
    if(mem.find(queTup)!=mem.end()){
		return mem[queTup];
	}
	return mem[queTup] = query(a,b,c,d);
}

vector<vector<bool> > same;
vi l;
vi r;
ll root;

ll findRoot(ll dn,ll up){
    rep(i,dn,up){
        if(makeQuery(i,i,dn,i)&&makeQuery(i,i,i,up-1)){
            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){
	mem.clear();
	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 / 37
• Subtask 2: 0 / 24
• Subtask 3: 0 / 39