Submission #725067

#	Time	Username	Problem	Language	Result	Execution time	Memory
725067		FatihSolak	ICC (CEOI16_icc)	C++17	100 / 100	130 ms	796 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"
#define N 105
using namespace std;
vector<int> adj[N];
vector<int> x;
bool vis[N];
int qu = 1625;
void dfs(int v){
    vis[v] = 1;
    x.push_back(v);
    for(auto u:adj[v]){
        if(!vis[u]){
            dfs(u);
        }
    }
}
/*
void setRoad(int a,int b){
    cout <<"ROAD: " <<  a << " " << b << endl;
    return;
}
int query(int sa,int sb,int a[],int b[]){
    for(int i=0;i<sa;i++){
        cout << a[i] << " ";
    }
    cout << endl;
    for(int i=0;i<sb;i++){
        cout << b[i] << " ";
    }
    cout << endl;
    int ret;
    cin >> ret;
    return ret;
}*/
void solve2(vector<int> l,vector<int> r){
    if(l.size() == 1 && r.size() == 1){
        setRoad(l[0],r[0]);
        adj[l[0]].push_back(r[0]);
        adj[r[0]].push_back(l[0]);
        return;
    }
    if(l.size() == 1){
        vector<int> a,b;
        for(int i=0;i<(int)(r.size()+1)/2;i++){
            a.push_back(r[i]);
        }
        for(int i=(r.size()+1)/2;i<(int)r.size();i++){
            b.push_back(r[i]);
        }
        int sum1 = 1,sum2 = a.size();
        int al[sum1],ar[sum2];
        al[0] = l[0];
        for(int i = 0;i<(int)sum2;i++){
            ar[i] = a[i];
        }
        qu--;
        assert(qu >= 0);
        if(query(sum1,sum2,al,ar)){
            solve2(l,a);
        }
        else solve2(l,b);
    }
    else{
        vector<int> a,b;
        for(int i=0;i<(int)(l.size()+1)/2;i++){
            a.push_back(l[i]);
        }
        for(int i=(l.size()+1)/2;i<(int)l.size();i++){
            b.push_back(l[i]);
        }
        int sum1 = a.size(),sum2 = r.size();
        int al[sum1],ar[sum2];
        for(int i = 0;i<(int)sum1;i++){
            al[i] = a[i];
        }
        for(int i = 0;i<(int)sum2;i++){
            ar[i] = r[i];
        }
        qu--;
        assert(qu >= 0);
        if(query(sum1,sum2,al,ar)){
            solve2(a,r);
        }
        else solve2(b,r);
    }
}
void go(vector<vector<vector<int>>> a,vector<vector<vector<int>>> b){
     vector<int> l,r;
    for(auto u:a){
        for(auto c:u){
            for(auto d:c)
                l.push_back(d);
        }
    }
    for(auto u:b){
        for(auto c:u){
            for(auto d:c)
                r.push_back(d);
        }
    }
    solve2(l,r);
}
void solve(vector<vector<int>> tmp){
    vector<vector<vector<int>>> v;
    v.push_back(tmp);
    while(1){
        vector<vector<vector<int>>> a,b;
        int sum1 = 0;
        int sum2 = 0;
        for(auto comps:v){
            vector<vector<int>> l,r;
            for(int i=0;i<(int)comps.size()/2;i++){
                l.push_back(comps[i]);
                sum1 += comps[i].size();
            }
            for(int i=comps.size()/2;i<(int)comps.size();i++){
                r.push_back(comps[i]);
                sum2 += comps[i].size();
            }
            a.push_back(l);
            b.push_back(r);
        }
        int l[sum1],r[sum2];
        int cnt = 0;
        for(auto u:a){
            for(auto c:u){
                for(auto d:c){
                    l[cnt++] = d;
                }
            }
        }
        cnt = 0;
        for(auto u:b){
            for(auto c:u){
                for(auto d:c){
                    r[cnt++] = d;
                }
            }
        }
 
        qu--;
        assert(qu >= 0);
        if(query(sum1,sum2,l,r)){
            go(a,b);
            return;
        }
        v = a;
        for(auto u:b)v.push_back(u);
    }
}
void run(int n){
    srand(time(NULL));
    for(int i = 1;i<n;i++){
        vector<vector<int>> comps;
        for(int j=1;j<=n;j++){
            vis[j] = 0;
        }
        for(int j=1;j<=n;j++){
            if(!vis[j]){
                x.clear();
                dfs(j);
                comps.push_back(x);
            }
        }
        random_shuffle(comps.begin(),comps.end());
        solve(comps);
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10