oj.uz

Submission #162157

# Submission time Handle Problem Language Result Execution time Memory
162157 2019-11-06T18:26:41 Z alexandra_udristoiu ICC (CEOI16_icc) C++14
100 / 100
 162 ms 632 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 504 KB Ok! 123 queries used.
2 Correct 9 ms 504 KB Ok! 122 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 552 KB Ok! 661 queries used.
2 Correct 45 ms 504 KB Ok! 606 queries used.
3 Correct 48 ms 504 KB Ok! 666 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 552 KB Ok! 1624 queries used.
2 Correct 138 ms 552 KB Ok! 1413 queries used.
3 Correct 150 ms 604 KB Ok! 1625 queries used.
4 Correct 162 ms 504 KB Ok! 1614 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 504 KB Ok! 1613 queries used.
2 Correct 147 ms 552 KB Ok! 1616 queries used.
3 Correct 147 ms 552 KB Ok! 1625 queries used.
4 Correct 150 ms 632 KB Ok! 1617 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 556 KB Ok! 1596 queries used.
2 Correct 147 ms 504 KB Ok! 1625 queries used.
3 Correct 146 ms 504 KB Ok! 1559 queries used.
4 Correct 150 ms 560 KB Ok! 1625 queries used.
5 Correct 155 ms 556 KB Ok! 1625 queries used.
6 Correct 149 ms 632 KB Ok! 1622 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 556 KB Ok! 1625 queries used.
2 Correct 151 ms 556 KB Ok! 1625 queries used.