Submission #38827

#	Time	Username	Problem	Language	Result	Execution time	Memory
38827		cheater2k	ICC (CEOI16_icc)	C++14	61 / 100	209 ms	2220 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"
using namespace std;

const int MX = 110;
vector <int> a, G[MX];
vector <int> comp[MX];
vector <int> rd;
int n, pos[MX];

void reset() {
    for (int i = 1; i <= n; ++i) comp[i].clear(), pos[i] = 0; a.clear(); rd.clear();
}

void dfs(int u, int p) {
    comp[p].push_back(u); if (u == p) a.push_back(u); pos[u] = p;
    for (int i = 0; i < G[u].size(); ++i) {
        int v = G[u][i]; if (!pos[v]) dfs(v, p);
    }
}

int V[2][MX];
void convert(vector <int> v, int num) {
    for (int i = 0; i < v.size(); ++i) V[num][i] = v[i];
}

vector <int> A, B;
int find_vertex(int l, int r) {
    if (l == r) return A[l];
    int mid = ((l + r) >> 1);
    vector <int> na;
    for (int i = 0; i < A.size(); ++i) if (l <= i && i <= mid) na.push_back(A[i]);
    convert(na, 0);
    if (query(na.size(), B.size(), V[0], V[1])) return find_vertex(l, mid);
    else return find_vertex(mid + 1, r);
}

void solve() {
    reset();
    for (int i = 1; i <= n; ++i) if (pos[i] == 0) pos[i] = i, dfs(i, i);
    int sz = a.size(); for (int i = 0; i < sz; ++i) rd.push_back(i);
    while(1) {
        random_shuffle(rd.begin(), rd.end());
        A.clear(); B.clear();
        for (int i = 0; i < sz / 2; ++i) for (int j = 0; j < comp[a[rd[i]]].size(); ++j) A.push_back(comp[a[rd[i]]][j]);
        for (int i = sz / 2; i < sz; ++i) for (int j = 0; j < comp[a[rd[i]]].size(); ++j) B.push_back(comp[a[rd[i]]][j]);
        convert(A, 0), convert(B, 1);
        if (query(A.size(), B.size(), V[0], V[1])) break;
     }
    int u = find_vertex(0, A.size()-1);
    A.swap(B); convert(B, 1);
    int v = find_vertex(0, A.size()-1);
    setRoad(u, v);
    G[u].push_back(v); G[v].push_back(u);
}

void run(int N) {
    srand(time(NULL));
    n = N;
    for (int i = 1; i < n; ++i) solve();
}

Compilation message (stderr)

icc.cpp: In function 'void dfs(int, int)':
icc.cpp:17:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < G[u].size(); ++i) {
                       ^
icc.cpp: In function 'void convert(std::vector<int>, int)':
icc.cpp:24:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i) V[num][i] = v[i];
                       ^
icc.cpp: In function 'int find_vertex(int, int)':
icc.cpp:32:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < A.size(); ++i) if (l <= i && i <= mid) na.push_back(A[i]);
                       ^
icc.cpp: In function 'void solve()':
icc.cpp:45:60: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < sz / 2; ++i) for (int j = 0; j < comp[a[rd[i]]].size(); ++j) A.push_back(comp[a[rd[i]]][j]);
                                                            ^
icc.cpp:46:61: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = sz / 2; i < sz; ++i) for (int j = 0; j < comp[a[rd[i]]].size(); ++j) B.push_back(comp[a[rd[i]]][j]);
                                                             ^

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10