제출 #604595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
604595		nghiass001	ICC (CEOI16_icc)	C++17	0 / 100	2 ms	852 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], list_a[N], list_b[N], color[N];
vector<vector<int>> Q;
vector<int> Q2[N];

int 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);
        REP(i, 0, tmp) Q2[i] = Q[i];

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

int ask(int lft, int rgt) {
    int sza = 0, szb = 0;
    FOR(id, lft, rgt) {
        for(int i : Q[id]) {
            if (id % 2 == 0) list_a[sza++] = i;
            else list_b[szb++] = i;
        }
    }
    return query(sza, szb, list_a, list_b);
}

int ask2(int id, int lx, int rx, int ly, int ry) {
    int sza = 0, szb = 0;
    FOR(i, lx, rx) list_a[sza++] = Q[id * 2][i];
    FOR(i, ly, ry) list_b[szb++] = Q[id * 2 + 1][i];
    return query(sza, szb, list_a, list_b);
}

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);
        int lft = 0, rgt = div2() / 2 - 1, mid;
        while (lft < rgt) {
            mid = (lft + rgt) / 2;
            if (ask(lft, mid) == 1) rgt = mid;
            else lft = mid + 1;
        }

        int lx = 0, rx = Q[lft * 2].size() - 1;
        int ly = 0, ry = Q[lft * 2 + 1].size() - 1;

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

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

        setRoad(Q[lft * 2][lx], Q[lft * 2 + 1][ly]);
        FOR(i, 1, n) if (dad[i] == Q[lft * 2 + 1][ly]) dad[i] = dad[Q[lft * 2][lx]];
    }
}

컴파일 시 표준 에러 (stderr) 메시지

icc.cpp: In function 'int 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:22:13: note: in expansion of macro 'REP'
   22 |             REP(j, mid, Q[i].size()) color[Q[i][j]] = i * 2 + 1;
      |             ^~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10