Submission #94996

#	Time	Username	Problem	Language	Result	Execution time	Memory
94996		georgerapeanu	ICC (CEOI16_icc)	C++11	7 / 100	2077 ms	636 KiB

icc

#include "icc.h"
 
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <cstdio>
#include <iostream>
 
using namespace std;
 
vector<vector<int>> components;
 
int a[200],len_a;
int b[200],len_b;
int c[200],len_c;
int d[200],len_d;
 
const int LIM = 2;
const int ATTEMPTS = 1000;

int n;
int adia[200][200];
int curr[200][200];
int in_a[200];
int in_b[200];
 
int pre_query(int len_a,int len_b,int a[],int b[],bool cost_mode = false){

    if(cost_mode){
        int total = 0,info = 0;
        for(int i = 1;i <= len_a;i++){
            for(int j = 1;j <= len_b;j++){
                total += (adia[i][j] == -1);
            }
        }
        bool is_true = false;
        for(int i = 0;i < len_a;i++){
            for(int j = 0;j < len_b;j++){
                info += (adia[a[i]][b[j]] == -1);
                is_true |= (adia[a[i]][b[j]] == 1);
            }
        }
        if(is_true){
            info = 0;
        }
        return min(info,total - info);
    }
 
    if(len_a == 0 || len_b == 0){
        return 0;
    }
 
    bool is_true = false;
    bool is_unknown = false;

    for(int i = 0;i < len_a;i++){
        for(int j = 0;j < len_b;j++){
            is_true |= (adia[a[i]][b[j]] == 1);
            is_unknown |= (adia[a[i]][b[j]] == -1);
        }
    }
 
    if(is_true == true){
        return 1;
    }

    if(is_unknown == false){
        return false;
    }
 
    int ans = query(len_a,len_b,a,b);

    if(ans == 0){
        for(int i = 0;i < len_a;i++){
            for(int j = 0;j < len_b;j++){
                adia[a[i]][b[j]] = 0;
            }
        }
    }
    else{
        for(int i = 1;i <= n;i++){
            in_a[i] = false;
            in_b[i] = false;
        }

        for(int i = 0;i < len_a;i++){
            in_a[a[i]] = true;        
        }

        for(int j = 0;j < len_b;j++){
            in_b[b[j]] = true;
        }

        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                if(adia[i][j] == -1){
                    if((in_a[i] == false || in_b[j] == false) && (in_a[j] == false || in_b[i] == false)){
                        adia[i][j] = 0;
                    }
                }
            }
        }
    }

    return ans;
}
 
int my_query(vector<int> &c1,vector<int> &c2,bool cost_mode = false){
    
    len_a = 0;
    for(auto it:c1){
        a[len_a++] = it;
    }
 
    len_b = 0;
    for(auto it:c2){
        b[len_b++] = it;
    }
 
    return pre_query(len_a,len_b,a,b,cost_mode);
}
 
int my_query(vector< vector<int> > &c1,vector< vector<int> > &c2,bool cost_mode = false){
    len_a = 0;
    for(auto it:c1){
        for(auto it2:it){
            a[len_a++] = it2;
        }
    }
    
    len_b = 0;
    for(auto it:c2){
        for(auto it2:it){
            b[len_b++] = it2;
        }
    }
 
    return pre_query(len_a,len_b,a,b,cost_mode);
}
 
void get_split(vector< vector<int> > &c1,vector< vector<int> > &c2){
    vector< vector<int> > total;
    vector< vector<int> > best1,best2;
    int cost = 1 << 30;

    for(auto it:c1){
        total.push_back(it);
    }

    for(auto it:c2){
        total.push_back(it);
    }

    for(int i = 1;i <= ATTEMPTS;i++){
        random_shuffle(total.begin(),total.end());
        vector< vector<int> > now1,now2;
        now2 = total;
        reverse(now2.begin(),now2.end());
        for(int i = 0;i < (int)total.size();i++){
            now2.pop_back();
            now1.push_back(total[i]);
            int tmp = my_query(now1,now2,true);
            if(tmp < cost){
                cost = tmp;
                best1 = now1;
                best2 = now2;
            }
        }
    }

    c1 = best1;
    c2 = best2;
}

void run(int N){
    n = N;
 
    srand(time(NULL));
    for(int i = 1;i <= n;i++){
        components.push_back({i});    
    } 
 
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            adia[i][j] = (i == j ? 1:-1);
        }
    }
    
    for(int t = 1;t < n;t++){
        random_shuffle(components.begin(),components.end());
        vector<vector<int>> c1,c2;
        for(int i = 0;i < (int)components.size() / 2;i++){
            c1.push_back(components[i]);
        }
        for(int i = (int)components.size() / 2;i < (int)components.size();i++){
            c2.push_back(components[i]);
        }
 
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                adia[i][j] = (adia[i][j] == 1 ? 1:-1);
            }
        }

        while(c1.size() + c2.size() > LIM){
            while(my_query(c1,c2) == 0){
                get_split(c1,c2); 
            }
 
            vector<vector<int>> nc1,nc2,nc3,nc4;
            
            for(int i = 0;i < (int)c1.size() / 2;i++){
                nc1.push_back(c1[i]);
            }
 
            for(int i = (int)c1.size() / 2;i < (int)c1.size();i++){
                nc2.push_back(c1[i]);
            }
 
            for(int i = 0;i < (int)c2.size() / 2;i++){
                nc3.push_back(c2[i]);
            }
 
            for(int i = (int)c2.size() / 2;i < (int)c2.size();i++){
                nc4.push_back(c2[i]);
            }
        
            if(my_query(c1,nc3)){
                swap(c2,nc3);
                if(my_query(nc1,c2)){
                    swap(c1,nc1);
                }
                else{
                    swap(c1,nc2);
                }
            }
            else{
                swap(c2,nc4);
                if(my_query(nc1,c2)){
                    swap(c1,nc1);
                }
                else{
                    swap(c1,nc2);
                }
            }
        }
       
        vector<int> fst_comp = c1[0];
        vector<int> snd_comp = c2[0];
 
        for(auto &it:components){
            if(it == snd_comp){
                swap(it,components.back());
            }
        }
 
        components.pop_back();
 
        for(auto &it:components){
            if(it == fst_comp){
                for(auto it2:snd_comp){
                    it.push_back(it2);
                }
            }
        }
 
        while((int)fst_comp.size() + (int)snd_comp.size() > LIM){
            vector<int> nc1,nc2,nc3,nc4;
 
            for(int i = 0;i < (int)fst_comp.size() / 2;i++){
                nc1.push_back(fst_comp[i]);
            }
 
            for(int i = (int)fst_comp.size() / 2;i < (int)fst_comp.size();i++){
                nc2.push_back(fst_comp[i]);
            }
            
            for(int i = 0;i < (int)snd_comp.size() / 2;i++){
                nc3.push_back(snd_comp[i]);
            }
 
            for(int i = (int)snd_comp.size() / 2;i < (int)snd_comp.size();i++){
                nc4.push_back(snd_comp[i]);
            }
 
            if(my_query(fst_comp,nc3)){
                swap(snd_comp,nc3);
                if(my_query(nc1,snd_comp)){
                    swap(fst_comp,nc1);
                }
                else{
                    swap(fst_comp,nc2);
                }
            }
            else{
                swap(snd_comp,nc4);
                if(my_query(nc1,snd_comp)){
                    swap(fst_comp,nc1);
                }
                else{
                    swap(fst_comp,nc2);
                }
            }
        }

        for(auto it:c1[0]){
            for(auto it2:c2[0]){
                adia[it][it2] = 1;
                adia[it2][it] = 1;
            }
        }

        setRoad(fst_comp[0],snd_comp[0]);

    }
}
 

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