oj.uz

Submission #129720

# Submission time Handle Problem Language Result Execution time Memory
129720 2019-07-13T05:44:35 Z BThero Library (JOI18_library) C++17
19 / 100
 2000 ms 472 KB 
// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include "library.h"

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;   
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MAXN = (int)1e3 + 5;

vector<int> V[MAXN], S;

int par[MAXN];

int getPar(int x) {
    if (x == par[x]) {
        return x;
    }
    else {
        return par[x] = getPar(par[x]);
    }
}

void uni(int a, int b) {
    a = getPar(a);
    b = getPar(b);

    if (a == b) {
        return;
    }

    par[b] = a;

    for (int x : V[b]) {
        V[a].pb(x);
    }

    V[b].clear();
    int p = 0;

    while (S[p] != b) {
        ++p;
    }

    S.erase(S.begin() + p);
}

void Solve(int n) {
    vector<int> ask, p(n);

    for (int i = 0; i < n; ++i) {
        p[i] = i;
    }

    for (int step = 0; step < 10; ++step) {
        random_shuffle(all(p));
    }

    for (int i = 0; i < n; ++i) {
        par[i] = i;
        V[i].pb(i);
    }

    S.pb(p[0]);
    int prev = 1;

    for (int i = 1; i < n; ++i) {
        ask = vector<int>(n, 0);

        for (int j = 0; j <= i; ++j) {
            ask[p[j]] = 1;
        }

        int cur = Query(ask);
        S.pb(p[i]);
        
        if (cur == prev) {
            for (int id : S) {
                if (id == p[i]) {
                    continue;
                }

                ask = vector<int>(n, 0);
                ask[p[i]] = 1;
                ask[V[id].front()] = 1;

                if (Query(ask) == 1) {
                    uni(p[i], id);
                    break;
                }

                ask = vector<int>(n, 0);
                ask[p[i]] = 1;
                ask[V[id].back()] = 1;

                if (Query(ask) == 1) {
                    uni(id, p[i]);
                    break;
                }
            }
        }
        else if (cur == prev - 1) {
            int a = -1, b = -1;

            for (int id : S) {
                if (id == p[i]) {
                    continue;
                }

                ask = vector<int>(n, 0);
                ask[p[i]] = 1;
                ask[V[id].front()] = 1;

                if (Query(ask) == 1) {
                    if (b != -1) {
                        reverse(all(V[id]));
                        a = id;
                    }
                    else {
                        b = id;
                    }
                }
                else {
                    ask = vector<int>(n, 0);
                    ask[p[i]] = 1;
                    ask[V[id].back()] = 1;

                    if (Query(ask) == 1) {
                        if (a != -1) {
                            reverse(all(V[id]));
                            b = id;
                        }
                        else {
                            a = id;
                        }
                    }
                }
            }

            uni(a, p[i]);
            uni(a, b);
        }

        prev = cur;
    }

    int v = 0;

    while (getPar(v) != v) {
        ++v;
    }

    for (int &x : V[v]) {
        ++x;
    }

	Answer(V[v]);
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 348 KB # of queries: 6388
2 Correct 127 ms 348 KB # of queries: 6634
3 Correct 89 ms 376 KB # of queries: 7267
4 Correct 122 ms 352 KB # of queries: 7496
5 Correct 114 ms 376 KB # of queries: 6232
6 Correct 107 ms 376 KB # of queries: 6492
7 Correct 124 ms 376 KB # of queries: 7273
8 Correct 90 ms 348 KB # of queries: 6649
9 Correct 118 ms 248 KB # of queries: 6899
10 Correct 52 ms 248 KB # of queries: 3155
11 Correct 2 ms 376 KB # of queries: 0
12 Correct 2 ms 376 KB # of queries: 2
13 Correct 2 ms 376 KB # of queries: 5
14 Correct 2 ms 376 KB # of queries: 6
15 Correct 2 ms 376 KB # of queries: 55
16 Correct 4 ms 248 KB # of queries: 143

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 348 KB # of queries: 6388
2 Correct 127 ms 348 KB # of queries: 6634
3 Correct 89 ms 376 KB # of queries: 7267
4 Correct 122 ms 352 KB # of queries: 7496
5 Correct 114 ms 376 KB # of queries: 6232
6 Correct 107 ms 376 KB # of queries: 6492
7 Correct 124 ms 376 KB # of queries: 7273
8 Correct 90 ms 348 KB # of queries: 6649
9 Correct 118 ms 248 KB # of queries: 6899
10 Correct 52 ms 248 KB # of queries: 3155
11 Correct 2 ms 376 KB # of queries: 0
12 Correct 2 ms 376 KB # of queries: 2
13 Correct 2 ms 376 KB # of queries: 5
14 Correct 2 ms 376 KB # of queries: 6
15 Correct 2 ms 376 KB # of queries: 55
16 Correct 4 ms 248 KB # of queries: 143
17 Execution timed out 3060 ms 468 KB Time limit exceeded
18 Execution timed out 3015 ms 396 KB Time limit exceeded
19 Execution timed out 3084 ms 396 KB Time limit exceeded
20 Execution timed out 3033 ms 404 KB Time limit exceeded
21 Execution timed out 3059 ms 384 KB Time limit exceeded
22 Execution timed out 3014 ms 392 KB Time limit exceeded
23 Execution timed out 3009 ms 392 KB Time limit exceeded
24 Incorrect 974 ms 472 KB Wrong Answer [3]
25 Execution timed out 3058 ms 392 KB Time limit exceeded
26 Execution timed out 3013 ms 388 KB Time limit exceeded
27 Incorrect 970 ms 376 KB Wrong Answer [3]
28 Execution timed out 3074 ms 396 KB Time limit exceeded
29 Execution timed out 3033 ms 376 KB Time limit exceeded
30 Execution timed out 3025 ms 392 KB Time limit exceeded