oj.uz

Submission #570073

# Submission time Handle Problem Language Result Execution time Memory
570073 2022-05-28T14:03:38 Z MatijaL ICC (CEOI16_icc) C++17
18 / 100
 298 ms 500 KB 
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
typedef long long ll;
#define pll pair<ll, ll>
#define loop(i, n) for(ll i = 0; i < n; i++)
#define FOR(i,n,m) for(ll i = n; i <= m; i++)
#define isIn(vec, item) find(vec.begin(), vec.end(), item) != vec.end()
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define inf 1500000005
#define mod 1500000007
#define print(v) for(auto e : v) cout << e << " "; cout << endl;

int cnt=0;
/*
int query(int s_a, int s_b, int a[], int b[]){
    printf("Query\n");
    FOR(i, 0, s_a-1) printf("%d ", a[i]);
    printf("\n");
    FOR(i, 0, s_b-1) printf("%d ", b[i]);
    printf("\n");
    cnt++;
    int ans;
    cin >> ans;
    return ans;
}

void setRoad(int a, int b){
    printf("Set road %d %d\n",a ,b);
}*/

int par[200], sz[200];
int find(ll a){
    if(par[a]==a)return a;
    return par[a]=find(par[a]);
}
void un(int a, int b){
    a=find(a);b=find(b);
    if(a==b) return;
    if(sz[b]>sz[a]) swap(a, b);
    par[b]=a;
    sz[a]+=sz[b];
}
vector<int> cmp;
set<int> comps;

bool comp_query(vector<int> a, vector<int> b){
    vector<int> u, v;
    for(auto e : a){
        FOR(i, 1, 150){
            if(find(i)==e)u.pb(i);
        }
    }
    for(auto e : b){
        FOR(i, 1, 150){
            if(find(i)==e)v.pb(i);
        }
    }
    if(min(u.size(), v.size())==0) return false;
    return query(u.size(), v.size(), &u[0], &v[0]);
}

bool out=0;
pll f(int l, int r){
    if(l>=r || out) return mp(0, 0);
    vector<int> a, b;
    int m=(l+r)/2;
    FOR(i, l, m) a.pb(cmp[i]);
    FOR(i, m+1, r) b.pb(cmp[i]);
    bool ans = comp_query(a, b);
    if(ans) {out=1;return mp(l, r);}
    else if(l+1==r) return mp(0,0);
    else return max(f(l, m), f(m+1, r));
}

int g(int l, int r, int l_b, int r_b){
    vector<int> b;
    FOR(i, l_b, r_b)b.pb(cmp[i]);
    int m;
    while(l!=r){
        m=(l+r)/2;
        vector<int> a;
        FOR(i, l, m) a.pb(cmp[i]);
        bool ans=comp_query(a, b);
        if(ans)r=m;
        else l=m+1;
    }
    return l;
}

int h(int A, int B){
    vector<int> b;
    FOR(i, 1, 150) if(find(i)==B)b.pb(i);
    vector<int> v;
    FOR(i, 1, 150) if(find(i)==A)v.pb(i);
    int l=0, r=v.size()-1;
    int m;
    while(l!=r){
        m=(l+r)/2;
        vector<int> a;
        FOR(i, l, m) a.pb(v[i]);
        bool ans=query(a.size(), b.size(), &a[0], &b[0]);
        if(ans) r=m;
        else l=m+1;
    }
    return v[l];
}



void run(int N){
    //setup
    FOR(i, 1, 150) {par[i]=i;sz[i]=1;}
    loop(_n, N-1){

        //find components
        comps.clear(); cmp.clear();
        FOR(i, 1, N) comps.insert(find(i));
        for(auto e : comps) cmp.pb(e);
        int M = cmp.size();

        //query
        out=0;
        auto [l,r] = f(0, M-1);
        int m = (l+r)/2;

        int A = g(l, m, m+1, r);
        int B = g(m+1, r, A, A);

        //printf("Found comps %d %d\n", cmp[A], cmp[B]);

        int X = h(cmp[A], cmp[B]);
        int Y = h(cmp[B], cmp[A]);
        setRoad(X, Y);
        un(X, Y);
    }
    //printf("cnt=%d\n", cnt);
}


/*
int main(){
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    
    int _N;
    cin >> _N;
    run(_N);
     
}*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Ok! 110 queries used.
2 Correct 10 ms 500 KB Ok! 121 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 488 KB Ok! 1090 queries used.
2 Correct 66 ms 496 KB Ok! 1413 queries used.
3 Correct 67 ms 484 KB Ok! 1430 queries used.

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 298 ms 492 KB Number of queries more than 4500 out of 2250
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 258 ms 500 KB Number of queries more than 4000 out of 2000
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 241 ms 496 KB Number of queries more than 3550 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 213 ms 484 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -