Submission #96066

#	Time	Username	Problem	Language	Result	Execution time	Memory
96066		georgerapeanu	ICC (CEOI16_icc)	C++11	7 / 100	2061 ms	176652 KiB

icc

#include "icc.h"
 
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <cstdio>
#include <iostream>
 
using namespace std;
 
const int NMAX = 1e2;

vector<vector<int>> components;
int label[2 * NMAX + 5];
int inv_label[2 * NMAX + 5];
 
int a[NMAX + 5],len_a;
int b[NMAX + 5],len_b;
int lg2[NMAX + 5];


int my_query(vector<int> &c1,vector<int> &c2){
    len_a = 0;
    for(auto it:c1){
        a[len_a++] = it;
    }
 
    len_b = 0;
    for(auto it:c2){
        b[len_b++] = it;
    }
 
    if(len_a == 0 || len_b == 0){
        return 0;
    }

    return query(len_a,len_b,a,b);
}
 
void run(int n){
    lg2[0] = -1;
    for(int i = 1;i <= n;i++){
        lg2[i] = 1 + lg2[i >> 1];
        components.push_back({i});    
    } 
    for(int t = 1;t < n;t++){
        int last_comp_bit = lg2[(int)components.size() - 1];
        int total_bits = last_comp_bit;
        for(int x = 0;x < (int)components.size();x++){
            for(int i = 0;i < (int)components[x].size();i++){
                label[components[x][i]] = ((i << (lg2[(int)components.size() - 1] + 1) | x));
                inv_label[((i << (lg2[(int)components.size() - 1] + 1) | x))] = components[x][i];
                total_bits = max(total_bits,last_comp_bit + 1 + lg2[i]);
            }
        }

        int m1 = 0;
        int m2 = 0;
        int xo = 0;

        for(int b = 0;b <= last_comp_bit;b++){
            vector<int> v1,v2;
            for(int i = 1;i <= n;i++){
                if((label[i] >> b) & 1){
                    v1.push_back(i);
                }
                else{
                    v2.push_back(i);
                }
            }
            
            xo |= my_query(v1,v2) << b;
        }

        int pos = 0;

        for(int b = 0;b <= last_comp_bit;b++){
            if((xo >> b) & 1){
                m1 = 1 << b;
                pos = b;
                break;
            }
        }

        for(int b = 0;b <= last_comp_bit;b++){
            if(b == pos){
                continue;
            }
            m2 |= ((((xo >> b) & 1)) << b);

            vector<int> v1,v2;

            for(int i = 1;i <= n;i++){
                if(((label[i] >> pos) & 1) == 1 && (((1 << (b + 1)) - 1) & label[i]) == (((1 << (b + 1)) - 1) & m1)){
                    v1.push_back(i);
                }
                else if(((label[i] >> pos) & 1) == 0 && (((1 << (b + 1)) - 1) & label[i]) == (((1 << (b + 1)) - 1) & m2)){
                    v2.push_back(i);
                }
            }

            if(my_query(v1,v2) == 0){
                m1 ^= (1 << b);
                m2 ^= (1 << b);
            }
        }
        
        int fst_comp = (m1 & ((1 << (last_comp_bit + 1)) - 1));
        int snd_comp = (m2 & ((1 << (last_comp_bit + 1)) - 1));
       
        int pref1 = -1,pref2 = -1;

        for(int b = total_bits;b >= 0;b--){
            if(pref1 + (1 << b) < (int)components[fst_comp].size()){
                vector<int> v;
                for(int i = 0;i <= pref1 + (1 << b);i++){
                    v.push_back(components[fst_comp][i]);
                }
                if(my_query(components[snd_comp],v) == 0){
                    pref1 += (1 << b);
                }
            }
        }
        
        for(int b = total_bits;b >= 0;b--){
            if(pref2 + (1 << b) < (int)components[snd_comp].size()){
                vector<int> v;
                for(int i = 0;i <= pref2 + (1 << b);i++){
                    v.push_back(components[snd_comp][i]);
                }
                if(my_query(components[fst_comp],v) == 0){
                    pref2 += (1 << b);
                }
            }
        }

        int u = components[fst_comp][pref1 + 1];
        int v = components[snd_comp][pref2 + 1];
        
        setRoad(u,v);
        
        for(auto it:components[fst_comp]){
            components[snd_comp].push_back(it);
        }
        swap(components[fst_comp],components.back());
        components.pop_back();
    }
}
 

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