oj.uz

Submission #1083812

# Submission time Handle Problem Language Result Execution time Memory
1083812 2024-09-04T07:57:33 Z alexdumitru ICC (CEOI16_icc) C++14
61 / 100
 131 ms 620 KB 
#include <bits/stdc++.h>
#include "icc.h"

using namespace std;

const int NMAX = 100;

mt19937 mt(1228495337);

int A[NMAX], B[NMAX];
int cnt1, cnt2;
int cmp[NMAX + 1];
vector<vector<int>> comp;

void run(int n) {
    comp.resize(n);
    for (int i = 0; i < n; i++)
        comp[i].push_back(i + 1);
    int nrc = n;
    for (int step = 1; step < n; step++) {

        bool diffHalfs = false;
        while (!diffHalfs) {
            cnt1 = cnt2 = 0;

            for (int i = 0; i < nrc; i++) {
                if (mt() % 2) {
                    for (int node : comp[i]) {
                        cmp[node] = i;
                        A[cnt1++] = node;
                    }
                } else {
                    for (int node : comp[i]) {
                        cmp[node] = i;
                        B[cnt2++] = node;
                    }
                }
            }

            diffHalfs = query(cnt1, cnt2, A, B);
        }

        int pos1, pos2;
        pos1 = cnt1 - 1;
        pos2 = cnt2 - 1;

        int st = 0;
        int dr = cnt1 - 2;
        while (st <= dr) {
            int mij = (st + dr) / 2;
            if (query(mij + 1, cnt2, A, B)) {
                pos1 = mij;
                dr = mij - 1;
            } else {
                st = mij + 1;
            }
        }

        st = 0;
        dr = cnt2 - 2;
        while (st <= dr) {
            int mij = (st + dr) / 2;
            if (query(cnt1, mij + 1, A, B)) {
                pos2 = mij;
                dr = mij - 1;
            } else {
                st = mij + 1;
            }
        }

        setRoad(A[pos1], B[pos2]);

        pos1 = cmp[A[pos1]];
        pos2 = cmp[B[pos2]];
        if (pos1 > pos2) swap(pos1, pos2);

        for (int node : comp[pos2])
            comp[pos1].push_back(node);
        for (int i = pos2; i + 1 < nrc; i++)
            comp[i] = comp[i + 1];

        nrc--;
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Ok! 117 queries used.
2 Correct 5 ms 604 KB Ok! 105 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 604 KB Ok! 547 queries used.
2 Correct 42 ms 604 KB Ok! 884 queries used.
3 Correct 33 ms 604 KB Ok! 810 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 620 KB Ok! 1542 queries used.
2 Correct 131 ms 604 KB Ok! 2144 queries used.
3 Correct 96 ms 604 KB Ok! 1717 queries used.
4 Correct 101 ms 604 KB Ok! 1737 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 620 KB Ok! 1637 queries used.
2 Correct 93 ms 620 KB Ok! 1607 queries used.
3 Correct 106 ms 604 KB Ok! 1850 queries used.
4 Correct 91 ms 604 KB Ok! 1570 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 110 ms 604 KB Too many queries! 1920 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 620 KB Too many queries! 1979 out of 1625
2 Halted 0 ms 0 KB -