oj.uz

Submission #605018

# Submission time Handle Problem Language Result Execution time Memory
605018 2022-07-25T12:18:51 Z SlavicG ICC (CEOI16_icc) C++17
90 / 100
 162 ms 508 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

/*
int query(int a, int b, int* aa, int* bb) {

}
*/

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int query(vector<int> a, vector<int> b) {
    int aa[(int)a.size()], bb[(int)b.size()];
    for(int i = 0; i < (int)a.size(); ++i) aa[i] = a[i];
    for(int i = 0; i < (int)b.size(); ++i) bb[i] = b[i];
    return query(a.size(), b.size(), aa, bb);
}
struct dsu {
    vector<int> p;
    dsu(int n) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
    }
    int get(int a) {return p[a] = (p[a] == a ? a : get(p[a]));}
    void uni(int a, int b) {
        a = get(a);
        b = get(b);
        if(a > b) swap(a, b);
        p[a] = b;
    }
};

void run(int n) {
    dsu d(n + 5);
    for(int times = 0; times < n - 1; ++times) {
        int st = -1;
        vector<int> v;
        for(int i = 1; i <= n; ++i) v.push_back(d.get(i));
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        vector<int> A, B;
        vector<int> bits;
        for(int bit = 0; (1 << bit) < n; ++bit) bits.push_back(bit);
        shuffle(bits.begin(), bits.end(), rng);
        int mn = INT_MAX;
        for(int bit: bits) {
            vector<int> c1, c2;
            for(int i = 1; i <= n; ++i) {
                if((d.get(i) - 1) & (1 << bit)) c1.push_back(i);
                else c2.push_back(i);
            }
            if(c1.empty() || c2.empty()) continue;
            if(query(c1, c2)) {
                if(ceil(log2(c1.size())) + ceil(log2(c2.size())) < mn) {
                    mn = ceil(log2(c1.size())) + ceil(log2(c2.size()));
                    A = c1, B = c2;
                    break;
                }
            }
        }
        assert(A.size() > 0 && B.size() > 0);
        shuffle(A.begin(), A.end(), rng);
        shuffle(B.begin(), B.end(), rng);
        int ansA = -1, ansB = -1;
        int l = 0, r = (int)A.size() - 1;
        while(l <= r) {
            int mid = l + r >> 1;
            vector<int> paiu;
            for(int i = 0; i <= mid; ++i) paiu.push_back(A[i]);
            if(query(paiu, B)) {
                ansA = A[mid];
                r = mid - 1;
            } else l = mid + 1;
        }
        l = 0, r = (int)B.size() - 1;
        while(l <= r) {
            int mid = l + r >> 1;
            vector<int> paiu;
            for(int i = 0; i <= mid; ++i) paiu.push_back(B[i]);
            if(query(paiu, A)) {
                ansB = B[mid];
                r = mid - 1;
            } else l = mid + 1;
        }
        assert(ansA != -1 && ansB != -1);
        d.uni(ansA, ansB);
        setRoad(ansA, ansB);
    }
}

/*
int main() {
    int n; cin >> n;
    run(n);
}
*/

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:68:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |             int mid = l + r >> 1;
      |                       ~~^~~
icc.cpp:78:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |             int mid = l + r >> 1;
      |                       ~~^~~
icc.cpp:37:13: warning: unused variable 'st' [-Wunused-variable]
   37 |         int st = -1;
      |             ^~

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 468 KB Ok! 547 queries used.
2 Correct 44 ms 468 KB Ok! 729 queries used.
3 Correct 41 ms 488 KB Ok! 685 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 492 KB Ok! 1437 queries used.
2 Correct 156 ms 492 KB Ok! 1772 queries used.
3 Correct 115 ms 508 KB Ok! 1485 queries used.
4 Correct 123 ms 488 KB Ok! 1571 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 492 KB Ok! 1480 queries used.
2 Correct 129 ms 492 KB Ok! 1538 queries used.
3 Correct 153 ms 500 KB Ok! 1683 queries used.
4 Correct 114 ms 492 KB Ok! 1415 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 484 KB Ok! 1662 queries used.
2 Correct 162 ms 480 KB Ok! 1712 queries used.
3 Correct 146 ms 488 KB Ok! 1732 queries used.
4 Correct 136 ms 492 KB Ok! 1652 queries used.
5 Correct 123 ms 496 KB Ok! 1494 queries used.
6 Correct 147 ms 484 KB Ok! 1620 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 133 ms 496 KB Too many queries! 1686 out of 1625
2 Halted 0 ms 0 KB -