oj.uz

Submission #129734

# Submission time Handle Problem Language Result Execution time Memory
129734 2019-07-13T06:04:27 Z BThero Library (JOI18_library) C++17
0 / 100
 282 ms 768 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;
                int need = 0;

                for (int x : tmp) {
                    if (V[x].size() <= 2) {
                        ++need;
                    }
                    else {
                        need += 2;
                    }

                    ask[V[x].front()] = 1;
                    ask[V[x].back()] = 1;
                }

                if (Query(ask) != need) {
                    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;
            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;
                int need = 0;

                for (int x : tmp) {
                    if (V[x].size() <= 2) {
                        ++need;
                    }
                    else {
                        need += 2;
                    }

                    ask[V[x].front()] = 1;
                    ask[V[x].back()] = 1;
                }

                if (Query(ask) != need) {
                    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) {
                b = T[0];
            }
            else {
                a = T[0];
            }

            T.clear();

            for (int x : S) {
                if (x != a && x != b && 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;
                int need = 0;

                for (int x : tmp) {
                    if (V[x].size() <= 2) {
                        ++need;
                    }
                    else {
                        need += 2;
                    }

                    ask[V[x].front()] = 1;
                    ask[V[x].back()] = 1;
                }

                if (Query(ask) != need) {
                    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) {
                if (b != -1) {
                    reverse(all(V[T[0]]));
                    a = T[0];
                }
                else {
                    b = T[0];
                }
            }
            else {
                if (a != -1) {
                    reverse(all(V[T[0]]));
                    b = T[0];
                }
                else {
                    a = T[0];
                }
            }

            uni(a, p[i]);
            uni(p[i], 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:129:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int j = T.size() / 2; j < T.size(); ++j) {
                                                ~~^~~~~~~~~~
library.cpp:161:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j = 0; j < T.size() / 2; ++j) {
                                 ~~^~~~~~~~~~~~~~
library.cpp:184:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int j = T.size() / 2; j < T.size(); ++j) {
                                                ~~^~~~~~~~~~
library.cpp:214:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j = 0; j < T.size() / 2; ++j) {
                                 ~~^~~~~~~~~~~~~~
library.cpp:237: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 Incorrect 19 ms 356 KB Wrong Answer [8]
2 Incorrect 25 ms 440 KB Wrong Answer [8]
3 Incorrect 29 ms 376 KB Wrong Answer [8]
4 Incorrect 28 ms 428 KB Wrong Answer [8]
5 Incorrect 19 ms 348 KB Wrong Answer [8]
6 Incorrect 27 ms 376 KB Wrong Answer [8]
7 Incorrect 27 ms 356 KB Wrong Answer [8]
8 Incorrect 25 ms 504 KB Wrong Answer [8]
9 Incorrect 20 ms 352 KB Wrong Answer [8]
10 Incorrect 17 ms 248 KB Wrong Answer [8]
11 Correct 2 ms 376 KB # of queries: 0
12 Correct 2 ms 248 KB # of queries: 2
13 Correct 2 ms 376 KB # of queries: 4
14 Correct 2 ms 248 KB # of queries: 7
15 Correct 3 ms 248 KB # of queries: 47
16 Incorrect 4 ms 248 KB Wrong Answer [8]

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 356 KB Wrong Answer [8]
2 Incorrect 25 ms 440 KB Wrong Answer [8]
3 Incorrect 29 ms 376 KB Wrong Answer [8]
4 Incorrect 28 ms 428 KB Wrong Answer [8]
5 Incorrect 19 ms 348 KB Wrong Answer [8]
6 Incorrect 27 ms 376 KB Wrong Answer [8]
7 Incorrect 27 ms 356 KB Wrong Answer [8]
8 Incorrect 25 ms 504 KB Wrong Answer [8]
9 Incorrect 20 ms 352 KB Wrong Answer [8]
10 Incorrect 17 ms 248 KB Wrong Answer [8]
11 Correct 2 ms 376 KB # of queries: 0
12 Correct 2 ms 248 KB # of queries: 2
13 Correct 2 ms 376 KB # of queries: 4
14 Correct 2 ms 248 KB # of queries: 7
15 Correct 3 ms 248 KB # of queries: 47
16 Incorrect 4 ms 248 KB Wrong Answer [8]
17 Incorrect 273 ms 520 KB Wrong Answer [8]
18 Incorrect 264 ms 632 KB Wrong Answer [8]
19 Incorrect 282 ms 520 KB Wrong Answer [8]
20 Incorrect 250 ms 632 KB Wrong Answer [8]
21 Incorrect 195 ms 768 KB Wrong Answer [8]
22 Incorrect 270 ms 508 KB Wrong Answer [8]
23 Incorrect 278 ms 532 KB Wrong Answer [8]
24 Incorrect 89 ms 376 KB Wrong Answer [8]
25 Incorrect 262 ms 524 KB Wrong Answer [8]
26 Incorrect 241 ms 516 KB Wrong Answer [8]
27 Incorrect 101 ms 496 KB Wrong Answer [8]
28 Incorrect 252 ms 388 KB Wrong Answer [8]
29 Incorrect 255 ms 384 KB Wrong Answer [8]
30 Incorrect 282 ms 632 KB Wrong Answer [8]