oj.uz

Submission #57977

# Submission time Handle Problem Language Result Execution time Memory
57977 2018-07-16T15:01:52 Z gabrielsimoes ICC (CEOI16_icc) C++17
100 / 100
 168 ms 960 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

#ifndef __ICC_H__
int query(int a, int b, int *A, int *B) {
    printf("\nProgram queried:\n");
    printf("  A:");
    for (int i = 0; i < a; i++) printf(" %d", A[i]);
    printf("\n");
    printf("  B:");
    for (int i = 0; i < b; i++) printf(" %d", B[i]);
    printf("\n");

    printf("\nAre those two groups connected? ");
    int ans;
    scanf("%d", &ans);
    return ans;
}

void setRoad(int a, int b) {
    printf("\n!!! Program set road between %d and %d.\n", a, b);
}
#endif

const int MAXN = 101;

int n;
int component_number;
int uf[MAXN];

int get(int a) { return uf[a] == a ? a : uf[a] = get(uf[a]); }
void join(int a, int b) { uf[get(b)] = get(a); }

void split(vector<int> &source, vector<int> &l, vector<int> &r) {
    l.clear();
    r.clear();

    int mid = (int(source.size()) - 1) >> 1;
    for (int i = 0; i < source.size(); i++) {
        if (i <= mid) l.push_back(source[i]);
        else r.push_back(source[i]);
    }
}

void run(int _n) {
    srand(129312);

    n = _n;
    component_number = _n;

    for (int i = 1; i <= n; i++) uf[i] = i;

    while (component_number > 1) {
        vector<vector<int>> groups(1), new_groups;
        vector<int> a, b;
        bool component_direction[n+1];

        for (int i = 1; i <= n; i++) if (uf[i] == i) groups[0].push_back(i);

        while (true) {
            a.clear(); b.clear();
            new_groups.clear();

            for (vector<int> &v : groups) {
                int mid = (int(v.size()) - 1) >> 1;
                vector<int> new_l, new_r;
                for (int i = 0; i < v.size(); i++) {
                    if (i <= mid) {
                        component_direction[v[i]] = 0;
                        new_l.push_back(v[i]);
                    } else {
                        component_direction[v[i]] = 1;
                        new_r.push_back(v[i]);
                    }
                }
                new_groups.push_back(new_l);
                new_groups.push_back(new_r);
            }

            for (int i = 1; i <= n; i++) {
                if (component_direction[get(i)] == 0) a.push_back(i);
                else b.push_back(i);
            }

            if (query(a.size(), b.size(), a.data(), b.data())) break;

            swap(groups, new_groups);
        }

        vector<int> a_l, a_r, b_l, b_r;
        while (a.size() > 1 || b.size() > 1) {
            if (a.size() > 1) {
                split(a, a_l, a_r);
                if (query(a_l.size(), b.size(), a_l.data(), b.data())) swap(a, a_l);
                else swap(a, a_r);
            }

            if (b.size() > 1) {
                split(b, b_l, b_r);
                if (query(a.size(), b_l.size(), a.data(), b_l.data())) swap(b, b_l);
                else swap(b, b_r);
            }
        }

        setRoad(a[0], b[0]);
        join(a[0], b[0]);

        component_number--;
    }
}

#ifndef __ICC_H__
int main() {
    int n;
    printf("n? ");
    scanf("%d", &n);
    run(n);
}
#endif

Compilation message

icc.cpp: In function 'void split(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
icc.cpp:40:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < source.size(); i++) {
                     ~~^~~~~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:68:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int i = 0; i < v.size(); i++) {
                                 ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 504 KB Ok! 98 queries used.
2 Correct 10 ms 664 KB Ok! 108 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 664 KB Ok! 550 queries used.
2 Correct 52 ms 664 KB Ok! 637 queries used.
3 Correct 50 ms 724 KB Ok! 622 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 724 KB Ok! 1491 queries used.
2 Correct 161 ms 744 KB Ok! 1585 queries used.
3 Correct 141 ms 744 KB Ok! 1569 queries used.
4 Correct 158 ms 808 KB Ok! 1518 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 808 KB Ok! 1531 queries used.
2 Correct 131 ms 836 KB Ok! 1534 queries used.
3 Correct 144 ms 852 KB Ok! 1524 queries used.
4 Correct 144 ms 852 KB Ok! 1534 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 852 KB Ok! 1525 queries used.
2 Correct 149 ms 860 KB Ok! 1488 queries used.
3 Correct 150 ms 868 KB Ok! 1541 queries used.
4 Correct 168 ms 868 KB Ok! 1539 queries used.
5 Correct 156 ms 868 KB Ok! 1495 queries used.
6 Correct 165 ms 868 KB Ok! 1541 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 928 KB Ok! 1524 queries used.
2 Correct 138 ms 960 KB Ok! 1488 queries used.