oj.uz

Submission #604595

# Submission time Handle Problem Language Result Execution time Memory
604595 2022-07-25T07:58:58 Z nghiass001 ICC (CEOI16_icc) C++17
0 / 100
 2 ms 852 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], 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]];
    }
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 724 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -