Submission #725076

#	Time	Username	Problem	Language	Result	Execution time	Memory
725076		FatihSolak	ICC (CEOI16_icc)	C++17	100 / 100	147 ms	736 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);
                }
            }
            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