Submission #162157

#	Time	Username	Problem	Language	Result	Execution time	Memory
162157		alexandra_udristoiu	ICC (CEOI16_icc)	C++14	100 / 100	162 ms	632 KiB

icc

#include<iostream>
#include "icc.h"
using namespace std;
static int c[105], v1[105], v2[105], ff[20];
static void solve(int m1, int v1[], int m2, int v2[]){
    int i, mid;
    while(m1 > 1){
        mid = m1 / 2;
        if(query(mid, m2, v1, v2) == 1){
            m1 = mid;
        }
        else{
            for(i = mid; i < m1; i++){
                v1[i - mid] = v1[i];
            }
            m1 -= mid;
        }
    }
}
static int bit(int x, int i){
    return (1 & (x >> i) );
}
void run(int n){
    int nr, i, ii, m1, m2, k, j, x, y;
    nr = n;
    for(i = 1; i <= n; i++){
        c[i] = i;
    }
    for(k = 1; k < n; k++){
        for(ii = 0; (1 << ii ) <= nr; ii++){
            m1 = m2 = 0;
            for(i = 1; i <= n; i++){
                if( ( (c[i] >> ii) & 1) == 0){
                    v1[m1++] = i;
                }
                else{
                    v2[m2++] = i;
                }
            }
            if(query(m1, m2, v1, v2) == 1){
                ff[ii] = 1;
            }
            else{
                ff[ii] = 0;
            }
        }
        for(ii = ii - 1; ii >= 0; ii--){
            if(ff[ii] == 1){
                break;
            }
        }
        x = y = 0;
        for(i = 0; (1 << i) <= nr; i++){
            if(i == ii){
                y += (1 << i);
                continue;
            }
            m1 = m2 = 0;
            for(j = 1; j <= n; j++){
                if(bit(c[j], ii) == 0 && bit(c[j], i) == 0){
                    v1[m1++] = j;
                }
                if(bit(c[j], ii) == 1 && bit(c[j], i) == ff[i]){
                    v2[m2++] = j;
                }
            }
            if(query(m1, m2, v1, v2) == 1){
                y += (1 << i) * ff[i];
            }
            else{
                x += (1 << i);
                y += (1 << i) * (1 - ff[i]);
            }
        }
        m1 = m2 = 0;
        if(x > y){
            swap(x, y);
        }
        for(i = 1; i <= n; i++){
            if(c[i] == x){
                v1[m1++] = i;
            }
            else{
                if(c[i] == y){
                    v2[m2++] = i;
                    c[i] = x;
                }
                if(c[i] > y){
                    c[i]--;
                }
            }
        }
        solve(m1, v1, m2, v2);
        solve(m2, v2, m1, v1);
        setRoad(v1[0], v2[0]);
        nr--;
    }
}

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