oj.uz

Submission #129725

# Submission time Handle Problem Language Result Execution time Memory
129725 2019-07-13T05:50:37 Z BThero Library (JOI18_library) C++17
0 / 100
 554 ms 624 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) {
            vector<int> T;

            for (int x : S) {
                if (x != p[i]) {
                    T.pb(x);
                }
            }

            while (T.size() > 1) {
                vector<int> tmp;

                for (int j = 0; j < T.size() / 2; ++j) {
                    tmp.pb(T[j]);
                }

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

                for (int x : tmp) {
                    ask[V[x].front()] = 1;
                    ask[V[x].back()] = 1;
                }

                if (Query(ask) != tmp.size()) {
                    tmp.clear();

                    for (int j = T.size() / 2; j < T.size(); ++j) {
                        tmp.pb(T[j]);
                    }
                }
                
                T = tmp;
            }

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

            if (Query(ask) == 1) {
                uni(p[i], T[0]);
            }
            else {
                uni(T[0], p[i]);
            }
        }
        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]);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:106:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j = 0; j < T.size() / 2; ++j) {
                                 ~~^~~~~~~~~~~~~~
library.cpp:118:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (Query(ask) != tmp.size()) {
                     ~~~~~~~~~~~^~~~~~~~~~~~~
library.cpp:121:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int j = T.size() / 2; j < T.size(); ++j) {
                                                ~~^~~~~~~~~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 31 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Incorrect 91 ms 376 KB Wrong Answer [4]
4 Incorrect 99 ms 248 KB Wrong Answer [4]
5 Incorrect 67 ms 388 KB Wrong Answer [4]
6 Incorrect 95 ms 248 KB Wrong Answer [4]
7 Incorrect 67 ms 436 KB Wrong Answer [4]
8 Runtime error 25 ms 616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Incorrect 91 ms 376 KB Wrong Answer [4]
10 Incorrect 27 ms 348 KB Wrong Answer [4]
11 Correct 2 ms 376 KB # of queries: 0
12 Correct 2 ms 376 KB # of queries: 2
13 Correct 2 ms 248 KB # of queries: 4
14 Correct 2 ms 248 KB # of queries: 6
15 Correct 3 ms 296 KB # of queries: 47
16 Incorrect 4 ms 376 KB Wrong Answer [8]

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 31 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Incorrect 91 ms 376 KB Wrong Answer [4]
4 Incorrect 99 ms 248 KB Wrong Answer [4]
5 Incorrect 67 ms 388 KB Wrong Answer [4]
6 Incorrect 95 ms 248 KB Wrong Answer [4]
7 Incorrect 67 ms 436 KB Wrong Answer [4]
8 Runtime error 25 ms 616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Incorrect 91 ms 376 KB Wrong Answer [4]
10 Incorrect 27 ms 348 KB Wrong Answer [4]
11 Correct 2 ms 376 KB # of queries: 0
12 Correct 2 ms 376 KB # of queries: 2
13 Correct 2 ms 248 KB # of queries: 4
14 Correct 2 ms 248 KB # of queries: 6
15 Correct 3 ms 296 KB # of queries: 47
16 Incorrect 4 ms 376 KB Wrong Answer [8]
17 Incorrect 542 ms 400 KB Wrong Answer [3]
18 Incorrect 545 ms 392 KB Wrong Answer [3]
19 Runtime error 73 ms 520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 289 ms 516 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Incorrect 514 ms 392 KB Wrong Answer [3]
22 Runtime error 291 ms 520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Incorrect 503 ms 396 KB Wrong Answer [3]
24 Incorrect 362 ms 376 KB Wrong Answer [3]
25 Runtime error 313 ms 516 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 208 ms 516 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 36 ms 624 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Incorrect 486 ms 424 KB Wrong Answer [3]
29 Incorrect 515 ms 396 KB Wrong Answer [3]
30 Incorrect 554 ms 400 KB Wrong Answer [3]