Submission #166905

#	Time	Username	Problem	Language	Result	Execution time	Memory
166905		Leonardo_Paes	ICC (CEOI16_icc)	C++11	90 / 100	183 ms	596 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"

using namespace std;

const int maxn = 110;

int pai[maxn], siz[maxn];

bool mark[maxn];

int find(int x){
    if(pai[x] == x){
        return x;
    }
    return pai[x] = find(pai[x]);
}

void join(int a, int b){
    a = find(a), b = find(b);

    if(a==b) return;

    if(siz[a] > siz[b]) swap(a, b);

    pai[a] = b;
    siz[b] += siz[a];
}

void run(int n){
    for(int i=0; i<n; i++){
        pai[i] = i;
        siz[i] = 1;
    }

    for(int roads = 1; roads <= (n-1); roads++){
        for(int i=0; (1 << i)<=n; i++){
            int siza = 0, sizb = 0;

            vector<int> fakea, fakeb;

            for(int j=1; j<=n; j++){
                int rep = find(j);

                if(rep & (1 << i)){
                    fakea.push_back(j);
                    siza++;
                }
                else{
                    fakeb.push_back(j);
                    sizb++;
                }
            }

            int a[siza], b[sizb];

            for(int j=0; j<fakea.size(); j++){
                a[j] = fakea[j];
            }

            for(int j=0; j<fakeb.size(); j++){
                b[j] = fakeb[j];
            }

            int ans;

            if(i==n) ans = 1;
            else ans = query(siza, sizb, a, b);

            if(ans){
                int u, v;

                int ini = 1, meio, fim = siza;

                while(ini < fim){
                    meio = (ini + fim)/2;

                    int testa[meio];

                    for(int id = 0; id<meio; id++){
                        testa[id] = a[id];
                    }

                    if(query(meio, sizb, testa, b)){
                        fim = meio;
                    }
                    else{
                        ini = meio + 1;
                    }
                }

                u = a[ini-1];

                ini = 1, fim = sizb;

                while(ini < fim){
                    meio = (ini + fim)/2;

                    int testb[meio];

                    for(int id = 0; id<meio; id++){
                        testb[id] = b[id];
                    }

                    if(query(siza, meio, a, testb)){
                        fim = meio;
                    }
                    else{
                        ini = meio + 1;
                    }
                }

                v = b[ini-1];

                join(u, v);

                setRoad(u, v);
            }
        }
    }
}

Compilation message (stderr)

icc.cpp: In function 'void run(int)':
icc.cpp:57:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0; j<fakea.size(); j++){
                          ~^~~~~~~~~~~~~
icc.cpp:61:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0; j<fakeb.size(); j++){
                          ~^~~~~~~~~~~~~

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