oj.uz

Submission #288179

# Submission time Handle Problem Language Result Execution time Memory
288179 2020-09-01T09:36:17 Z Kastanda Library (JOI18_library) C++11
100 / 100
 377 ms 672 KB 
// M
#include<bits/stdc++.h>
#include "library.h"
using namespace std;
const int N = 1009;
vector < int > Adj[N];

void Solve(int n)
{
        for (int i = 1; i <= n; i ++)
        {
                if ((int)Adj[i].size() == 2)
                        continue;
                vector < int > vec;
                for (int j = i + 1; j <= n; j ++)
                        vec.push_back(j);
                if (!vec.size())
                        continue;

                int le = -1, ri = (int)vec.size() - 1, md;

                vector < int > M(n, 0);
                for (int j : vec)
                        M[j - 1] = 1;
                int wq1 = Query(M);
                M[i - 1] = 1;
                int wq2 = Query(M);
                if (wq1 < wq2)
                        continue;
                while (ri - le > 1)
                {
                        md = (le + ri) >> 1;
                        M = vector < int > (n, 0);
                        for (int j = 0; j <= md; j ++)
                                M[vec[j] - 1] = 1;
                        int t1 = Query(M);
                        M[i - 1] = 1;
                        int t2 = Query(M);
                        if (t1 < t2)
                                le = md;
                        else
                                ri = md;
                }
                Adj[i].push_back(vec[ri]);
                Adj[vec[ri]].push_back(i);
                if (wq1 == wq2)
                        continue;
                assert(wq1 > wq2);
                int id = ri;
                le = ri; ri = (int)vec.size() - 1;
                assert(id < ri);
                while (ri - le > 1)
                {
                        md = (le + ri) >> 1;
                        M = vector < int > (n, 0);
                        for (int j = id + 1; j <= md; j ++)
                                M[vec[j] - 1] = 1;
                        int t1 = Query(M);
                        M[i - 1] = 1;
                        int t2 = Query(M);
                        if (t1 < t2)
                                le = md;
                        else
                                ri = md;
                }
                Adj[i].push_back(vec[ri]);
                Adj[vec[ri]].push_back(i);
        }

        int nw = -1;
        for (int i = 1; i <= n; i ++)
                if ((int)Adj[i].size() == 1)
                        nw = i;
        if (n == 1)
                nw = 1;
        assert(nw != -1);
        int last = -1;
        vector < int > Rs = {nw};
        for (int i = 1; i < n; i ++)
        {
                int tobe = Adj[nw][0];
                if (tobe == last)
                        tobe = Adj[nw][1];
                last = nw;
                nw = tobe;
                Rs.push_back(nw);
        }
        Answer(Rs);
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 384 KB # of queries: 2794
2 Correct 44 ms 384 KB # of queries: 2796
3 Correct 43 ms 384 KB # of queries: 2942
4 Correct 43 ms 384 KB # of queries: 2982
5 Correct 42 ms 384 KB # of queries: 2948
6 Correct 41 ms 384 KB # of queries: 2944
7 Correct 33 ms 396 KB # of queries: 2948
8 Correct 39 ms 396 KB # of queries: 2850
9 Correct 43 ms 384 KB # of queries: 2952
10 Correct 24 ms 512 KB # of queries: 1730
11 Correct 0 ms 384 KB # of queries: 0
12 Correct 0 ms 384 KB # of queries: 2
13 Correct 1 ms 384 KB # of queries: 6
14 Correct 0 ms 384 KB # of queries: 10
15 Correct 2 ms 384 KB # of queries: 102
16 Correct 3 ms 384 KB # of queries: 234

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 384 KB # of queries: 2794
2 Correct 44 ms 384 KB # of queries: 2796
3 Correct 43 ms 384 KB # of queries: 2942
4 Correct 43 ms 384 KB # of queries: 2982
5 Correct 42 ms 384 KB # of queries: 2948
6 Correct 41 ms 384 KB # of queries: 2944
7 Correct 33 ms 396 KB # of queries: 2948
8 Correct 39 ms 396 KB # of queries: 2850
9 Correct 43 ms 384 KB # of queries: 2952
10 Correct 24 ms 512 KB # of queries: 1730
11 Correct 0 ms 384 KB # of queries: 0
12 Correct 0 ms 384 KB # of queries: 2
13 Correct 1 ms 384 KB # of queries: 6
14 Correct 0 ms 384 KB # of queries: 10
15 Correct 2 ms 384 KB # of queries: 102
16 Correct 3 ms 384 KB # of queries: 234
17 Correct 364 ms 428 KB # of queries: 19396
18 Correct 340 ms 504 KB # of queries: 19206
19 Correct 333 ms 384 KB # of queries: 19376
20 Correct 322 ms 504 KB # of queries: 18142
21 Correct 326 ms 508 KB # of queries: 17092
22 Correct 377 ms 672 KB # of queries: 19378
23 Correct 362 ms 648 KB # of queries: 19390
24 Correct 136 ms 636 KB # of queries: 8946
25 Correct 262 ms 508 KB # of queries: 18998
26 Correct 316 ms 504 KB # of queries: 17706
27 Correct 142 ms 384 KB # of queries: 8918
28 Correct 296 ms 656 KB # of queries: 17954
29 Correct 312 ms 532 KB # of queries: 17934
30 Correct 311 ms 504 KB # of queries: 17954