oj.uz

Submission #38827

# Submission time Handle Problem Language Result Execution time Memory
38827 2018-01-07T02:53:41 Z cheater2k ICC (CEOI16_icc) C++14
61 / 100
 209 ms 2220 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2080 KB Ok! 101 queries used.
2 Correct 6 ms 2084 KB Ok! 95 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2080 KB Ok! 519 queries used.
2 Correct 56 ms 2088 KB Ok! 832 queries used.
3 Correct 53 ms 2080 KB Ok! 787 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 2216 KB Ok! 1478 queries used.
2 Correct 209 ms 2216 KB Ok! 2135 queries used.
3 Correct 146 ms 2212 KB Ok! 1711 queries used.
4 Correct 146 ms 2220 KB Ok! 1683 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 2220 KB Ok! 1602 queries used.
2 Correct 149 ms 2216 KB Ok! 1665 queries used.
3 Correct 166 ms 2216 KB Ok! 1823 queries used.
4 Correct 136 ms 2216 KB Ok! 1606 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 166 ms 2216 KB Too many queries! 1900 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 179 ms 2212 KB Too many queries! 1929 out of 1625
2 Halted 0 ms 0 KB -