oj.uz

Submission #129693

# Submission time Handle Problem Language Result Execution time Memory
129693 2019-07-13T04:51:15 Z BThero Library (JOI18_library) C++17
19 / 100
 2000 ms 1008 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;

void Solve(int n) {
    vector<deque<int> > groups;
    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));
    }

    groups.pb(deque<int>({p[0]}));
    int prev = 1;

    for (int i = 1; i <= n; ++i) {
        // printf("GROUPS: %d\n", groups.size());

        // for (auto it : groups) {
        //     printf("{");

        //     for (int x : it) {
        //         printf("%d ", x);
        //     }

        //     printf("}\n");
        // }

        // printf("---\n");

        if (i == n) {
            break;
        }

        ask = vector<int>(n, 0);

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

        int cur = Query(ask);

        if (cur == prev + 1) {
            groups.pb(deque<int>({p[i]}));
        }
        else if (cur == prev) {
            for (auto &it : groups) {
                ask = vector<int>(n, 0);
                ask[p[i]] = 1;
                ask[it.front()] = 1;

                if (Query(ask) == 1) {
                    it.push_front(p[i]);
                    break;
                }

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

                if (Query(ask) == 1) {
                    it.pb(p[i]);
                    break;
                }
            }
        }
        else {
            vector<deque<int> > tmp;
            deque<int> A, B;

            for (auto &it : groups) {
                ask = vector<int>(n, 0);
                ask[p[i]] = 1;
                ask[it.front()] = 1;

                if (Query(ask) == 1) {
                    if (!B.empty()) {
                        reverse(all(it));
                        A = it;
                    }
                    else {
                        B = it;
                    }
                }
                else {
                    ask = vector<int>(n, 0);
                    ask[p[i]] = 1;
                    ask[it.back()] = 1;

                    if (Query(ask) == 1) {
                        if (!A.empty()) {
                            reverse(all(it));
                            B = it;
                        }
                        else {
                            A = it;
                        }
                    }
                    else {
                        tmp.pb(it);
                    }
                }
            }

            A.pb(p[i]);

            for (int x : B) {
                A.pb(x);
            }

            tmp.pb(A);
            groups = tmp;
        }

        prev = cur;
    }

    vector<int> ret;

    for (int x : groups[0]) {
        ret.pb(x + 1);
    }

	Answer(ret);
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 320 KB # of queries: 6662
2 Correct 135 ms 512 KB # of queries: 6885
3 Correct 102 ms 316 KB # of queries: 7400
4 Correct 131 ms 376 KB # of queries: 7017
5 Correct 111 ms 408 KB # of queries: 6354
6 Correct 122 ms 376 KB # of queries: 6493
7 Correct 120 ms 504 KB # of queries: 7161
8 Correct 120 ms 376 KB # of queries: 6504
9 Correct 141 ms 448 KB # of queries: 7237
10 Correct 43 ms 460 KB # of queries: 3190
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: 5
14 Correct 2 ms 248 KB # of queries: 6
15 Correct 3 ms 248 KB # of queries: 55
16 Correct 4 ms 252 KB # of queries: 141

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 320 KB # of queries: 6662
2 Correct 135 ms 512 KB # of queries: 6885
3 Correct 102 ms 316 KB # of queries: 7400
4 Correct 131 ms 376 KB # of queries: 7017
5 Correct 111 ms 408 KB # of queries: 6354
6 Correct 122 ms 376 KB # of queries: 6493
7 Correct 120 ms 504 KB # of queries: 7161
8 Correct 120 ms 376 KB # of queries: 6504
9 Correct 141 ms 448 KB # of queries: 7237
10 Correct 43 ms 460 KB # of queries: 3190
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: 5
14 Correct 2 ms 248 KB # of queries: 6
15 Correct 3 ms 248 KB # of queries: 55
16 Correct 4 ms 252 KB # of queries: 141
17 Execution timed out 3040 ms 648 KB Time limit exceeded
18 Execution timed out 3092 ms 736 KB Time limit exceeded
19 Execution timed out 3044 ms 668 KB Time limit exceeded
20 Execution timed out 3087 ms 1008 KB Time limit exceeded
21 Execution timed out 2866 ms 784 KB Time limit exceeded
22 Execution timed out 3081 ms 900 KB Time limit exceeded
23 Execution timed out 3083 ms 720 KB Time limit exceeded
24 Incorrect 755 ms 548 KB Wrong Answer [3]
25 Execution timed out 3080 ms 836 KB Time limit exceeded
26 Execution timed out 3032 ms 680 KB Time limit exceeded
27 Incorrect 734 ms 504 KB Wrong Answer [3]
28 Execution timed out 3061 ms 880 KB Time limit exceeded
29 Execution timed out 3093 ms 676 KB Time limit exceeded
30 Execution timed out 3018 ms 904 KB Time limit exceeded