oj.uz

Submission #367256

# Submission time Handle Problem Language Result Execution time Memory
367256 2021-02-16T17:03:52 Z mihai145 ICC (CEOI16_icc) C++14
100 / 100
 155 ms 700 KB 
//
// Created by mihai145 on 16.02.2021.
//

#include <vector>
#include <cmath>
#include "icc.h"

using namespace std;

const int NMAX = 100;
int comp[NMAX + 2];

void run(int N) {
    for(int i = 1; i <= N; i++) {
        comp[i] = i - 1;
    }

    for(int c = N; c > 1; c--) {
        int log = log2(c);

        vector<int> A, B;

        for(int bit = 0; bit <= log; bit++) {
            vector<int> a, b;
            for(int i = 1; i <= N; i++) {
                if (comp[i] & (1 << bit))
                    a.push_back(i);
                else
                    b.push_back(i);
            }

            int q = query((int)a.size(), (int)b.size(), a.data(), b.data());
            if(q) {
                A = a;
                B = b;
                break;
            }
        }

        for(int step = 1; step <= 2; step++) {
            while((int)A.size() > 1) {
                vector<int> A1, A2;
                for(int i = 0; i < (int)A.size(); i++) {
                    if(i % 2 == 0) {
                        A1.push_back(A[i]);
                    } else {
                        A2.push_back(A[i]);
                    }
                }

                int q = query((int)A1.size(), (int)B.size(), A1.data(), B.data());

                if(q) {
                    A = A1;
                } else {
                    A = A2;
                }
            }

            swap(A, B);
        }

        setRoad(A[0], B[0]);

        int cA = comp[A[0]], cB = comp[B[0]];

        for(int i = 1; i <= N; i++)
            if(comp[i] == cA) {
                comp[i] = cB;
            }
        
        for(int i = 1; i <= N; i++)
            if(comp[i] == c - 1) {
                comp[i] = cA;
            }
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 492 KB Ok! 96 queries used.
2 Correct 7 ms 492 KB Ok! 98 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 492 KB Ok! 536 queries used.
2 Correct 46 ms 492 KB Ok! 631 queries used.
3 Correct 44 ms 492 KB Ok! 643 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 492 KB Ok! 1458 queries used.
2 Correct 140 ms 620 KB Ok! 1546 queries used.
3 Correct 136 ms 492 KB Ok! 1569 queries used.
4 Correct 133 ms 700 KB Ok! 1509 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 620 KB Ok! 1547 queries used.
2 Correct 137 ms 620 KB Ok! 1560 queries used.
3 Correct 135 ms 620 KB Ok! 1563 queries used.
4 Correct 130 ms 492 KB Ok! 1517 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 492 KB Ok! 1591 queries used.
2 Correct 135 ms 620 KB Ok! 1542 queries used.
3 Correct 140 ms 620 KB Ok! 1571 queries used.
4 Correct 134 ms 492 KB Ok! 1562 queries used.
5 Correct 131 ms 620 KB Ok! 1500 queries used.
6 Correct 132 ms 492 KB Ok! 1517 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 572 KB Ok! 1560 queries used.
2 Correct 144 ms 492 KB Ok! 1569 queries used.