oj.uz

Submission #1117055

# Submission time Handle Problem Language Result Execution time Memory
1117055 2024-11-22T19:34:49 Z gustavo_d ICC (CEOI16_icc) C++17
7 / 100
 213 ms 760 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100;
vector<int> adj[MAXN+1];
bool vis[MAXN+1];

void dfs(int v) {
    vis[v] = true;
    for (int viz : adj[v]) {
        if (!vis[viz]) dfs(viz);
    }
}
// TODO: estudar flag pra debugar interativo
// void setRoad(int a, int b) {
//     cout << "report" << a << ' ' << b << endl;
// };

int do_query(vector<int> a, vector<int> b) {
    int tmp[MAXN], tmp2[MAXN];
    for (int i=0; i<(int)a.size(); i++) tmp[i] = a[i];
    for (int i=0; i<(int)b.size(); i++) tmp2[i] = b[i];
    // for (int i : a) cout << i << ' ';
    // cout << endl;
    // for (int i : b) cout << i << ' ';
    // cout << endl;
    // int v; cin >> v;
    // return v;
    return query((int)a.size(), (int)b.size(), tmp, tmp2);
}

void run(int N) {
    srand(time(0));
    int n = N;
    for (int e=0; e<n-1; e++) {
        // bool found = false;
        // for (int a=1; a<=n and !found; a++) {
        //     for (int b=a+1; b<=n and !found; b++) {
        //         if (do_query(vector<int> (1, a), vector<int> (1, b))) {
        //             setRoad(a, b);
        //             found = true;
        //         }
        //     }
        // }
        vector<int> src(n);
        for (int i=0; i<n; i++) src[i] = i+1;
        random_shuffle(src.begin(), src.end());
        int a = 0; vector<int> dest;
        for (int v : src) {
            dfs(v);
            for (int i=1; i<=n; i++) {
                if (!vis[i]) dest.push_back(i);
            }
            for (int i=1; i<=n; i++) vis[i] = false;
            a = v;
            if (do_query(vector<int> (1, v), dest)) break;
            dest.clear();
        }
        while (dest.size() > 1) {
            vector<int> dest2;
            for (int i=0; i<(int)dest.size() / 2; i++) {
                dest2.push_back(dest[i]);
            }
            if (do_query(vector<int> (1, a), dest2)) {
                swap(dest, dest2);
            } else {
                reverse(dest.begin(), dest.end());
                while(!dest2.empty()) {
                    dest2.pop_back(); dest.pop_back();
                }
            }
        }
        int b = dest[0];
        setRoad(a, dest[0]);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
}

// int main() {
//     int n; cin >> n;
//     run(n);
//     return 0;
// }

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 632 KB Ok! 223 queries used.
2 Correct 8 ms 592 KB Ok! 198 queries used.

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 592 KB Ok! 2473 queries used.
2 Incorrect 95 ms 592 KB Too many queries! 2546 out of 2500
3 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 213 ms 636 KB Number of queries more than 4500 out of 2250
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 191 ms 760 KB Number of queries more than 4000 out of 2000
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 170 ms 636 KB Number of queries more than 3550 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 154 ms 624 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -