oj.uz

Submission #162123

# Submission time Handle Problem Language Result Execution time Memory
162123 2019-11-06T14:41:55 Z alexandra_udristoiu ICC (CEOI16_icc) C++14
90 / 100
 187 ms 632 KB 
#include<iostream>
#include "icc.h"
using namespace std;
static int c[105], v1[105], v2[105];
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;
        }
    }
}
void run(int n){
    int nr, i, ii, m1, m2, k, 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){
                break;
            }
        }
        m1 = m2 = 0;
        for(i = 1; i <= n; i++){
            if( ( (c[i] >> ii) & 1) == 0){
                v1[m1++] = i;
            }
            else{
                v2[m2++] = i;
            }
        }
        solve(m1, v1, m2, v2);
        solve(m2, v2, m1, v1);
        x = v1[0];
        y = v2[0];
        setRoad(x, y);
        if(c[x] > c[y]){
            swap(x, y);
        }
        for(i = 1; i <= n; i++){
            if(i != y && c[i] == c[y]){
                c[i] = c[x];
            }
            else{
                if(c[i] > c[y]){
                    c[i]--;
                }
            }
        }
        c[y] = c[x];
        nr--;
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 504 KB Ok! 96 queries used.
2 Correct 9 ms 504 KB Ok! 102 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 504 KB Ok! 531 queries used.
2 Correct 54 ms 504 KB Ok! 669 queries used.
3 Correct 52 ms 504 KB Ok! 664 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 560 KB Ok! 1484 queries used.
2 Correct 172 ms 632 KB Ok! 1661 queries used.
3 Correct 161 ms 564 KB Ok! 1563 queries used.
4 Correct 158 ms 504 KB Ok! 1539 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 504 KB Ok! 1562 queries used.
2 Correct 151 ms 504 KB Ok! 1532 queries used.
3 Correct 165 ms 564 KB Ok! 1590 queries used.
4 Correct 152 ms 564 KB Ok! 1535 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 556 KB Ok! 1639 queries used.
2 Correct 162 ms 504 KB Ok! 1597 queries used.
3 Correct 169 ms 560 KB Ok! 1647 queries used.
4 Correct 157 ms 504 KB Ok! 1588 queries used.
5 Correct 148 ms 504 KB Ok! 1521 queries used.
6 Correct 152 ms 632 KB Ok! 1544 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 568 KB Ok! 1599 queries used.
2 Incorrect 168 ms 484 KB Too many queries! 1664 out of 1625