Submission #604668

#	Time	Username	Problem	Language	Result	Execution time	Memory
604668		nghiass001	ICC (CEOI16_icc)	C++17	100 / 100	182 ms	608 KiB

icc

#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 (stderr)

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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10