oj.uz

Submission #141110

# Submission time Handle Problem Language Result Execution time Memory
141110 2019-08-06T18:40:56 Z shayan_p ICC (CEOI16_icc) C++14
100 / 100
 151 ms 632 KB 
// only miss the sun when it starts to snow

#include<bits/stdc++.h>

#include "icc.h"

#define unit icc

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=110,mod=1e9+7;
const ll inf=1e18;

int bos[maxn], n;
vector<int> v[maxn], A, B, vec, vec0, vec1;

int arr1[maxn], arr2[maxn];

bool ask(){
    if(sz(A)==0 || sz(B)==0) return 0;
    int N=sz(A), M=sz(B);

    for(int i=0;i<N;i++)
	arr1[i]= A[i]+1;
    for(int i=0;i<M;i++)
	arr2[i]= B[i]+1;
    return query(N,M,arr1,arr2);
}
void operator += (vector<int>&a,vector<int>&b){
    for(int x:b) a.PB(x);
}
void Merge(int a,int b){
    a=bos[a], b=bos[b];
    if(sz(v[a]) < sz(v[b])) swap(a,b);
    for(int x:v[b]) bos[x]=a, v[a].PB(x);
    v[b].clear();
}
int solve(vector<int> &v1, vector<int>&v2){
    int bt=32-__builtin_clz(sz(v1));
    B=v2;
    int ans=0;
    
    for(int i=0;i<bt;i++){
	A.clear();
	for(int j=0;j<sz(v1);j++)
	    if(bit(j,i)) A.PB(v1[j]);
	if(ask()) ans^=(1<<i);
    }
    return v1[ans];
}
void proc(){
    vec.clear();
    for(int i=0;i<n;i++){
	if(bos[i]==i) vec.PB(i);
    }
    int bt=32-__builtin_clz(sz(vec));

    int df=-1;

    vector<int> rndm(bt);
    for(int i=0;i<bt;i++)
	rndm[i]=i;
    random_shuffle(rndm.begin(), rndm.end() );

    int bts=0;
    
    for(int i:rndm){
	A.clear(), B.clear();
	for(int j=0;j<sz(vec);j++){
	    if(bit(j,i)) A+= v[vec[j]];
	    else B+= v[vec[j]];
	}
	if(ask()){
	    df=i;
	    break;
	}
	else{
	    bts^=(1<<i);
	}
    }
    assert(df!=-1);

    vec0=A, vec1=B;
    int u=solve(vec0,vec1);
    
    vec0.clear(), vec0.PB(u);
    vec1.clear();

    int id=-1;
    for(int i=0;i<sz(vec);i++){
	if(vec[i] == bos[u]) id=i;
    }
    assert(id!=-1);
    
    for(int i=0;i<sz(vec);i++){
	if(bit(i,df)) continue;
	for(int j=0;j<bt;j++){
	    if(bit(bts,j) && bit(i,j)!=bit(id,j)) goto Hell;
	}
	vec1+= v[vec[i]];
    Hell:;
    }
    
    int v=solve(vec1,vec0);

    setRoad(u+1,v+1), Merge(u,v);
}

void run(int N){
    srand(time(0));
    ::n=N;
    for(int i=0;i<n;i++)
	bos[i]=i, v[i].PB(i);
    for(int i=0;i<n-1;i++)
	proc();
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 504 KB Ok! 96 queries used.
2 Correct 9 ms 556 KB Ok! 105 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 556 KB Ok! 551 queries used.
2 Correct 49 ms 504 KB Ok! 622 queries used.
3 Correct 47 ms 504 KB Ok! 623 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 632 KB Ok! 1428 queries used.
2 Correct 149 ms 560 KB Ok! 1571 queries used.
3 Correct 136 ms 596 KB Ok! 1445 queries used.
4 Correct 147 ms 504 KB Ok! 1514 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 564 KB Ok! 1355 queries used.
2 Correct 142 ms 560 KB Ok! 1461 queries used.
3 Correct 145 ms 504 KB Ok! 1508 queries used.
4 Correct 132 ms 504 KB Ok! 1324 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 508 KB Ok! 1498 queries used.
2 Correct 148 ms 504 KB Ok! 1571 queries used.
3 Correct 151 ms 560 KB Ok! 1571 queries used.
4 Correct 150 ms 504 KB Ok! 1573 queries used.
5 Correct 142 ms 504 KB Ok! 1489 queries used.
6 Correct 141 ms 504 KB Ok! 1508 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 632 KB Ok! 1577 queries used.
2 Correct 148 ms 504 KB Ok! 1577 queries used.