oj.uz

답안 #1028776

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1028776 2024-07-20T08:32:22 Z serifefedartar CEOI16_icc (CEOI16_icc) C++17
90 / 100
 103 ms 672 KB 
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;

mt19937 mt(chrono::system_clock::now().time_since_epoch().count());
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define LOGN 20
const ll MOD = 1e9 + 7;
const ll MAXN = 105;

int par[MAXN], sz[MAXN], temp1[MAXN], temp2[MAXN];
int find(int node) {
    if (node == par[node])
        return node;
    return par[node] = find(par[node]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b)
        return ;
    if (sz[b] > sz[a])
        swap(a, b);
    sz[a] += sz[b];
    par[b] = a;
}

int qry(int sz1, int sz2, vector<int> A, vector<int> B) {
    for (int i = 0; i < sz1; i++)
        temp1[i] = A[i];
    for (int i = 0; i < sz2; i++)
        temp2[i] = B[i];
    return query(sz1, sz2, temp1, temp2);
}

int n;
void match(vector<vector<int>> arr) {
    while (true) {
        shuffle(arr.begin(), arr.end(), mt);

        for (int rep = 0; rep < 10; rep++) {
            vector<int> A, B;
            for (int i = 0; i < arr.size(); i++) {
                if (i & (1<<rep)) {
                    for (auto u : arr[i])
                        A.push_back(u);
                } else {
                    for (auto u : arr[i])
                        B.push_back(u);
                }
            }

            if (qry(A.size(), B.size(), A, B)) {
                shuffle(A.begin(), A.end(), mt);
                shuffle(B.begin(), B.end(), mt);
                while ((int)B.size() > 1) {
                    vector<int> X, Y;
                    for (int i = 0; i < (int)B.size() / 2; i++)
                        X.push_back(B[i]);
                    for (int i = (int)B.size() / 2; i < (int)B.size(); i++)
                        Y.push_back(B[i]);

                    if (qry(A.size(), X.size(), A, X))
                        B = X;
                    else
                        B = Y;
                }

                while ((int)A.size() > 1) {
                    vector<int> X, Y;
                    for (int i = 0; i < (int)A.size() / 2; i++)
                        X.push_back(A[i]);
                    for (int i = (int)A.size() / 2; i < (int)A.size(); i++)
                        Y.push_back(A[i]);

                    if (qry(X.size(), 1, X, B))
                        A = X;
                    else
                        A = Y;
                }

                setRoad(B[0], A[0]);
                unite(B[0], A[0]);

                return ;
            }
        }
    }
}

void solve() {
    map<int, vector<int>> mp;
    for (int i = 1; i <= n; i++)
        mp[find(i)].push_back(i);

    vector<vector<int>> temp;
    for (auto u : mp)
        temp.push_back(u.s);

    match(temp);
}

void run(int N) {
    n = N;
    for (int i = 1; i <= N; i++)
        sz[i] = 1, par[i] = i;
    for (int i = 1; i < N; i++)
        solve();
}

Compilation message

icc.cpp: In function 'void match(std::vector<std::vector<int> >)':
icc.cpp:47:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             for (int i = 0; i < arr.size(); i++) {
      |                             ~~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 600 KB Ok! 98 queries used.
2 Correct 4 ms 640 KB Ok! 96 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 604 KB Ok! 541 queries used.
2 Correct 26 ms 600 KB Ok! 684 queries used.
3 Correct 26 ms 600 KB Ok! 661 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 600 KB Ok! 1438 queries used.
2 Correct 80 ms 604 KB Ok! 1630 queries used.
3 Correct 73 ms 672 KB Ok! 1542 queries used.
4 Correct 90 ms 604 KB Ok! 1517 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 600 KB Ok! 1543 queries used.
2 Correct 67 ms 644 KB Ok! 1522 queries used.
3 Correct 79 ms 604 KB Ok! 1627 queries used.
4 Correct 73 ms 604 KB Ok! 1482 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 600 KB Ok! 1613 queries used.
2 Correct 103 ms 656 KB Ok! 1642 queries used.
3 Correct 100 ms 604 KB Ok! 1653 queries used.
4 Correct 78 ms 664 KB Ok! 1620 queries used.
5 Correct 71 ms 644 KB Ok! 1498 queries used.
6 Correct 77 ms 604 KB Ok! 1553 queries used.

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 604 KB Ok! 1620 queries used.
2 Incorrect 81 ms 660 KB Too many queries! 1652 out of 1625
3 Halted 0 ms 0 KB -