Submission #725087

#	Time	Username	Problem	Language	Result	Execution time	Memory
725087		FatihSolak	ICC (CEOI16_icc)	C++17	100 / 100	116 ms	644 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"
#define N 105
using namespace std;
vector<int> adj[N];
vector<int> group[N];
bool ban[N][N];
bool vis[N];
int cnt = 0;
void run(int n){
    function<void(int)> dfs = [&](int v)->void{
        vis[v] = 1;
        group[cnt].push_back(v);
        for(auto u:adj[v]){
            if(!vis[u])
                dfs(u);
        }
    };
    for(int it = 1;it<n;it++){
        vector<vector<int>> l,r;
        vector<int> tmpl,tmpr;
        for(int i = 1;i<=n;i++){
            if(!vis[i]){
                cnt++;
                dfs(i);
                if(tmpl.size() < tmpr.size())
                    tmpl.push_back(cnt);
                else tmpr.push_back(cnt);
            }
        }
        l.push_back(tmpl);
        r.push_back(tmpr);
        while(1){
            int maxi = 0;
            for(auto &u:l)
                maxi = max(maxi,(int)u.size());
            for(auto &u:r)
                maxi = max(maxi,(int)u.size());
            if(maxi == 1)break;
            tmpl.clear();
            tmpr.clear();
            for(auto &u:l){
                for(auto c:u){
                    for(auto x:group[c]){
                        tmpl.push_back(x);
                    }
                }
            }
            for(auto &u:r){
                for(auto c:u){
                    for(auto x:group[c]){
                        tmpr.push_back(x);
                    }
                }
            }
            if(query(tmpl.size(),tmpr.size(),tmpl.data(),tmpr.data()))
                break;
            for(auto &u:l){
                for(auto c:u){
                    for(auto &x:r){
                        for(auto y:x){
                            ban[c][y] = 1;
                            ban[y][c] = 1;
                        }
                    }
                }
            }
            vector<vector<int>> nwl,nwr;
            int lsize = 0;
            int rsize = 0;
            for(auto &u:l){
                if(u.size() == 1)
                    continue;
                tmpl.clear();
                tmpr.clear();
                for(auto c:u){
                    if(tmpl.size() < tmpr.size())
                        tmpl.push_back(c);
                    else tmpr.push_back(c);
                }
                if(lsize < rsize){
                    nwl.push_back(tmpr);
                    nwr.push_back(tmpl);
                    lsize += tmpr.size();
                    rsize += tmpl.size();
                }
                else{
                    nwl.push_back(tmpl);
                    nwr.push_back(tmpr);
                    lsize += tmpl.size();
                    rsize += tmpr.size();
                }
            }
            for(auto &u:r){
                if(u.size() == 1)
                    continue;
                tmpl.clear();
                tmpr.clear();
                for(auto c:u){
                    if(tmpl.size() < tmpr.size())
                        tmpl.push_back(c);
                    else tmpr.push_back(c);
                }
                if(lsize < rsize){
                    nwl.push_back(tmpr);
                    nwr.push_back(tmpl);
                    lsize += tmpr.size();
                    rsize += tmpl.size();
                }
                else{
                    nwl.push_back(tmpl);
                    nwr.push_back(tmpr);
                    lsize += tmpl.size();
                    rsize += tmpr.size();
                }
            }
            l = nwl;
            r = nwr;
        }
        vector<int> ll,rr;
        for(auto &u:l){
            for(auto c:u){
                ll.push_back(c);
            }
        }
        while(ll.size() > 1){
            vector<int> a,b;
            for(auto c:ll){
                if(a.size() < b.size())
                    a.push_back(c);
                else b.push_back(c);
            }
            tmpl.clear();
            tmpr.clear();
            for(auto u:a){
                for(auto x:group[u]){
                    tmpl.push_back(x);
                }
            }
            for(auto &u:r){
                for(auto c:u){
                    for(auto x:group[c]){
                        tmpr.push_back(x);
                    }
                }
            }
            if(query(tmpl.size(),tmpr.size(),tmpl.data(),tmpr.data())){
                ll = a;
            }
            else ll = b;
        }
        for(auto &u:r){
            for(auto c:u){
                if(ban[ll[0]][c])continue;
                rr.push_back(c);
            }
        }
        while(rr.size() > 1){
            vector<int> a,b;
            for(auto c:rr){
                if(a.size() < b.size())
                    a.push_back(c);
                else b.push_back(c);
            }
            tmpl.clear();
            tmpr.clear();
            for(auto u:ll){
                for(auto x:group[u]){
                    tmpl.push_back(x);
                }
            }
            for(auto c:a){
                for(auto x:group[c]){
                    tmpr.push_back(x);
                }
            }
            if(query(tmpl.size(),tmpr.size(),tmpl.data(),tmpr.data())){
                rr = a;
            }
            else rr = b;
        }
        ll = group[ll[0]];
        rr = group[rr[0]];
        while(ll.size() > 1){
            vector<int> a,b;
            for(auto c:ll){
                if(a.size() < b.size())
                    a.push_back(c);
                else b.push_back(c);
            }
            if(query(a.size(),rr.size(),a.data(),rr.data())){
                ll = a;
            }
            else ll = b;
        }
        while(rr.size() > 1){
            vector<int> a,b;
            for(auto c:rr){
                if(a.size() < b.size())
                    a.push_back(c);
                else b.push_back(c);
            }
            if(query(ll.size(),a.size(),ll.data(),a.data())){
                rr = a;
            }
            else rr = b;
        }
        setRoad(ll[0],rr[0]);
        adj[ll[0]].push_back(rr[0]);
        adj[rr[0]].push_back(ll[0]);
        for(int i = 1;i<=n;i++){
            vis[i] = 0;
        }
        for(int i = 1;i<=cnt;i++){
            for(int j = 1;j<=cnt;j++){
                    ban[i][j] = 0;
            }
            group[i].clear();
        }
        cnt = 0;
    }
}

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