oj.uz

Submission #162155

# Submission time Handle Problem Language Result Execution time Memory
162155 2019-11-06T18:15:02 Z alexandra_udristoiu ICC (CEOI16_icc) C++14
61 / 100
 238 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 - 1) ) < 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 - 1) ) < 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 11 ms 504 KB Ok! 145 queries used.
2 Correct 11 ms 504 KB Ok! 144 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 504 KB Ok! 750 queries used.
2 Correct 50 ms 504 KB Ok! 690 queries used.
3 Correct 54 ms 632 KB Ok! 754 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 632 KB Ok! 1800 queries used.
2 Correct 153 ms 504 KB Ok! 1599 queries used.
3 Correct 166 ms 560 KB Ok! 1811 queries used.
4 Correct 168 ms 476 KB Ok! 1808 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 560 KB Ok! 1798 queries used.
2 Correct 238 ms 592 KB Ok! 1798 queries used.
3 Correct 170 ms 504 KB Ok! 1811 queries used.
4 Correct 172 ms 504 KB Ok! 1807 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 171 ms 504 KB Too many queries! 1811 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 632 KB Too many queries! 1811 out of 1625
2 Halted 0 ms 0 KB -