oj.uz

Submission #754924

# Submission time Handle Problem Language Result Execution time Memory
754924 2023-06-08T22:16:30 Z MilosMilutinovic ICC (CEOI16_icc) C++14
90 / 100
 140 ms 556 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 101;
int n, fa[N];
int gfa(int x) { return fa[x] == x ? x : fa[x] = gfa(fa[x]); }
//void setRoad(int x, int y) {
//    printf("new Road %d %d\n", x, y);
//}
bool query(vector<int> x, vector<int> y) {
    int sz_x = x.size();
    int sz_y = y.size();
    int qx[sz_x], qy[sz_y];
    for (int i = 0; i < sz_x; i++)
        qx[i] = x[i];
    for (int i = 0; i < sz_y; i++)
        qy[i] = y[i];
    return query(sz_x, sz_y, qx, qy);
//    printf("query\n");
//    for (int i : x) printf("%d ", i); printf("\n");
//    for (int i : y) printf("%d ", i); printf("\n");
//    int f;
//    scanf("%d", &f);
//    return f;
}
void add(vector<int>& v, int comp) {
    for (int i = 1; i <= n; i++)
        if (gfa(i) == gfa(comp))
            v.push_back(i);
}
pair<int, int> find_road(vector<int> a, vector<int> b) {
    pair<int, int> res;
    int low = 0, high = a.size() - 1, pos = 0;
    while (low <= high) {
        int mid = low + high >> 1;
        vector<int> q_vec;
        for (int i = 0; i <= mid; i++)
            q_vec.push_back(a[i]);
        if (query(q_vec, b))
            pos = mid, high = mid - 1;
        else
            low = mid + 1;
    }
    res.first = a[pos];
    low = 0, high = b.size() - 1;
    while (low <= high) {
        int mid = low + high >> 1;
        vector<int> q_vec;
        for (int i = 0; i <= mid; i++)
            q_vec.push_back(b[i]);
        if (query(q_vec, a))
            pos = mid, high = mid - 1;
        else
            low = mid + 1;
    }
    res.second = b[pos];
    return res;
}
void run(int n) {
    ::n = n;
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int iter = 1; iter <= n - 1; iter++) {
        vector<int> v;
        for (int i = 1; i <= n; i++)
            if (gfa(i) == i)
                v.push_back(i);
        int sz = (int) v.size(), lg = 0;
        while ((1 << lg) <= sz) lg++;
        int xr = 0;
        for (int b = 0; b < lg; b++) {
            vector<int> l, r;
            for (int i = 0; i < sz; i++) {
                if (i >> b & 1) {
                    add(l, v[i]);
                } else {
                    add(r, v[i]);
                }
            }
            if (query(l, r))
                xr ^= (1 << b);
        }
        int f = -1;
        for (int b = 0; b < lg; b++)
            if (xr >> b & 1)
                f = b;
        if (f == -1) while (true) {}
        int a = 0, b = 0;
        for (int i = 0; i < lg; i++) {
            if (xr >> i & 1) {
                if (i == f) {
                    a += (1 << i);
                    continue;
                }
                vector<int> l, r;
                for (int j = 0; j < sz; j++) {
                    if (j >> f & 1) {
                        if (j >> i & 1) add(l, v[j]);
                    } else {
                        if (!(j >> i & 1)) add(r, v[j]);
                    }
                }
                if (query(l, r))
                    a += (1 << i);
                else
                    b += (1 << i);
            } else {
                vector<int> l, r;
                for (int j = 0; j < sz; j++) {
                    if (j >> i & 1) continue;
                    if (j >> f & 1)
                        add(l, v[j]);
                    else
                        add(r, v[j]);
                }
                if (!query(l, r))
                    a += (1 << i), b += (1 << i);
            }
        }
        vector<int> l, r;
        for (int i = 1; i <= n; i++) {
            if (gfa(i) == v[a])
                l.push_back(i);
            if (gfa(i) == v[b])
                r.push_back(i);
        }
        pair<int, int> p = find_road(l, r);
        setRoad(p.first, p.second);
        fa[gfa(p.first)] = gfa(p.second);
    }
}

Compilation message

icc.cpp: In function 'std::pair<int, int> find_road(std::vector<int>, std::vector<int>)':
icc.cpp:35:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         int mid = low + high >> 1;
      |                   ~~~~^~~~~~
icc.cpp:47:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |         int mid = low + high >> 1;
      |                   ~~~~^~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 468 KB Ok! 141 queries used.
2 Correct 6 ms 468 KB Ok! 138 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 468 KB Ok! 711 queries used.
2 Correct 33 ms 556 KB Ok! 652 queries used.
3 Correct 40 ms 476 KB Ok! 714 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 492 KB Ok! 1721 queries used.
2 Correct 127 ms 484 KB Ok! 1532 queries used.
3 Correct 129 ms 468 KB Ok! 1731 queries used.
4 Correct 132 ms 480 KB Ok! 1706 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 496 KB Ok! 1708 queries used.
2 Correct 140 ms 484 KB Ok! 1703 queries used.
3 Correct 132 ms 500 KB Ok! 1731 queries used.
4 Correct 129 ms 500 KB Ok! 1718 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 488 KB Ok! 1679 queries used.
2 Correct 124 ms 492 KB Ok! 1731 queries used.
3 Correct 126 ms 500 KB Ok! 1671 queries used.
4 Correct 124 ms 488 KB Ok! 1731 queries used.
5 Correct 132 ms 500 KB Ok! 1718 queries used.
6 Correct 131 ms 500 KB Ok! 1730 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 125 ms 492 KB Too many queries! 1731 out of 1625
2 Halted 0 ms 0 KB -