oj.uz

Submission #604668

# Submission time Handle Problem Language Result Execution time Memory
604668 2022-07-25T08:40:36 Z nghiass001 ICC (CEOI16_icc) C++17
100 / 100
 182 ms 608 KB 
#include "icc.h"
#include <bits/stdc++.h>
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, l, r) for(int i = (l); i < (r); ++i)
#define FORD(i, r, l) for(int i = (r); i >= (l); --i)
using namespace std;
const int N = 1e2 + 5;
int n, dad[N], color[N];
vector<vector<int>> Q;
vector<int> list_a, list_b;

int query() {
  	int tmp = query(list_a.size(), list_b.size(), list_a.data(), list_b.data());
  	list_a.clear();
    list_b.clear();
    return tmp;
}

void div2() {
    int tmp = 1;
    while (true) {
        Q.clear();
        Q.resize(tmp);
        FOR(i, 1, n) if (dad[i] == i) Q[color[dad[i]]].push_back(i);
        REP(i, 0, tmp) {
            int mid = Q[i].size() / 2;
            random_shuffle(Q[i].begin(), Q[i].end());
            REP(j, 0, mid) color[Q[i][j]] = i * 2;
            REP(j, mid, Q[i].size()) color[Q[i][j]] = i * 2 + 1;
        }
        tmp *= 2;
        Q.clear();
        Q.resize(tmp);
        FOR(i, 1, n) Q[color[dad[i]]].push_back(i);

        int sza = 0, szb = 0;
        FOR(i, 1, n) {
            if (color[dad[i]] % 2 == 0) list_a.push_back(i);
            else list_b.push_back(i);
        }
        if (query()) break;
    }

    Q.clear();
    Q.resize(2);
    FOR(i, 1, n) Q[color[dad[i]] % 2].push_back(i);
}

int ask2(int lx, int rx, int ly, int ry) {
    FOR(i, lx, rx) list_a.push_back(Q[0][i]);
    FOR(i, ly, ry) list_b.push_back(Q[1][i]);
    return query();
}

void run(int nn) {
    srand(time(NULL));
    n = nn;
    FOR(i, 1, n) dad[i] = i;
    REP(step, 1, n) {
        fill(color + 1, color + n + 1, 0);
        div2();
        int mid;
        int lx = 0, rx = Q[0].size() - 1;
        int ly = 0, ry = Q[1].size() - 1;

        while (lx < rx) {
            mid = (lx + rx) / 2;
            if (ask2(lx, mid, ly, ry) == 1) rx = mid;
            else lx = mid + 1;
        }

        while (ly < ry) {
            mid = (ly + ry) / 2;
            if (ask2(lx, rx, ly, mid) == 1) ry = mid;
            else ly = mid + 1;
        }

        int tmp = dad[Q[1][ly]];
        FOR(i, 1, n) if (dad[i] == tmp) dad[i] = dad[Q[0][lx]];
        setRoad(Q[0][lx], Q[1][ly]);
    }
}

Compilation message

icc.cpp: In function 'void div2()':
icc.cpp:4:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define REP(i, l, r) for(int i = (l); i < (r); ++i)
      |                                         ^
icc.cpp:29:13: note: in expansion of macro 'REP'
   29 |             REP(j, mid, Q[i].size()) color[Q[i][j]] = i * 2 + 1;
      |             ^~~
icc.cpp:36:13: warning: unused variable 'sza' [-Wunused-variable]
   36 |         int sza = 0, szb = 0;
      |             ^~~
icc.cpp:36:22: warning: unused variable 'szb' [-Wunused-variable]
   36 |         int sza = 0, szb = 0;
      |                      ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Ok! 98 queries used.
2 Correct 9 ms 468 KB Ok! 100 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 500 KB Ok! 515 queries used.
2 Correct 49 ms 484 KB Ok! 637 queries used.
3 Correct 38 ms 476 KB Ok! 631 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 480 KB Ok! 1415 queries used.
2 Correct 182 ms 488 KB Ok! 1594 queries used.
3 Correct 124 ms 468 KB Ok! 1527 queries used.
4 Correct 128 ms 608 KB Ok! 1502 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 504 KB Ok! 1543 queries used.
2 Correct 134 ms 484 KB Ok! 1526 queries used.
3 Correct 128 ms 484 KB Ok! 1582 queries used.
4 Correct 115 ms 484 KB Ok! 1468 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 496 KB Ok! 1588 queries used.
2 Correct 126 ms 480 KB Ok! 1552 queries used.
3 Correct 121 ms 480 KB Ok! 1585 queries used.
4 Correct 128 ms 492 KB Ok! 1564 queries used.
5 Correct 107 ms 496 KB Ok! 1446 queries used.
6 Correct 124 ms 484 KB Ok! 1506 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 488 KB Ok! 1576 queries used.
2 Correct 126 ms 488 KB Ok! 1592 queries used.