Submission #57977

#	Time	Username	Problem	Language	Result	Execution time	Memory
57977		gabrielsimoes	ICC (CEOI16_icc)	C++17	100 / 100	168 ms	960 KiB

icc

#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 (stderr)

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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10