oj.uz

Submission #205196

# Submission time Handle Problem Language Result Execution time Memory
205196 2020-02-28T09:41:13 Z theStaticMind Library (JOI18_library) C++14
100 / 100
 372 ms 504 KB 
#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x.size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
//#define int long long int
using namespace std;

#include<library.h>

vector<int> Q(1001, 0);
int ind = 0;
int n;
int edge = 0;
vector<int> adj[1001];

int bin(int l, int r, int v, bool eq = true){
      int ret = -1;
      while(l <= r){
            int mid = (l + r) / 2;
            vector<int> arr(n, 0);
            for(int i = 0; i <= mid; i++)arr[i] = 1;
            for(int i = mid + 1; i < n; i++)arr[i] = 0;
            arr[v] = 1;

            if((eq && Query(arr) <= Q[mid]) || (!eq && Query(arr) < Q[mid])){
                  ret = mid;
                  r = mid - 1;
            }
            else{
                  l = mid + 1;
            }
      }
      return ret;
}

void Solve(int N){
      n = N;
      vector<int> arr(n, 0);

      for(;ind < n; ind++){
            arr[ind] = 1;
            Q[ind] = Query(arr);
            if(ind != 0 && Q[ind] <= Q[ind - 1]){
                  int x = bin(0, ind - 1, ind, true);
                  adj[x].pb(ind);
                  adj[ind].pb(x);
                  edge++;
                  x = bin(x + 1, ind - 1, ind, false);
                  if(x != -1){
                        edge++;
                        adj[x].pb(ind);
                        adj[ind].pb(x);
                  }
            }
      }

      int root = 0;
      while(sz(adj[root]) == 2)root++;

      vector<int> ans;
      int x = root;
      assert(root < n);
      assert(edge == n - 1);
      if(n == 1){
            ans.pb(1);
            Answer(ans);
            return;
      }
      for(int i = 0; i < n; i++){
            assert(sz(adj[x]));
            if(adj[x].size() == 1){
                  ans.pb(x+1);
                  x = adj[x][0];
            }
            else if(sz(adj[x]) == 2){
                  if(ans.back()-1 == adj[x][0]){
                        ans.pb(x+1);
                        x = adj[x][1];
                  }
                  else if(ans.back()-1 == adj[x][1]){
                        ans.pb(x+1);
                        x = adj[x][0];
                  }
                  else assert(0);
            }
            else assert(0);
      }
      Answer(ans);
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 376 KB # of queries: 1758
2 Correct 37 ms 348 KB # of queries: 1843
3 Correct 32 ms 248 KB # of queries: 1878
4 Correct 36 ms 248 KB # of queries: 1957
5 Correct 44 ms 348 KB # of queries: 1917
6 Correct 36 ms 248 KB # of queries: 1933
7 Correct 34 ms 248 KB # of queries: 1934
8 Correct 43 ms 376 KB # of queries: 1826
9 Correct 38 ms 376 KB # of queries: 1920
10 Correct 21 ms 376 KB # of queries: 1076
11 Correct 5 ms 248 KB # of queries: 1
12 Correct 5 ms 248 KB # of queries: 3
13 Correct 5 ms 376 KB # of queries: 6
14 Correct 5 ms 248 KB # of queries: 9
15 Correct 6 ms 248 KB # of queries: 65
16 Correct 8 ms 376 KB # of queries: 159

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 376 KB # of queries: 1758
2 Correct 37 ms 348 KB # of queries: 1843
3 Correct 32 ms 248 KB # of queries: 1878
4 Correct 36 ms 248 KB # of queries: 1957
5 Correct 44 ms 348 KB # of queries: 1917
6 Correct 36 ms 248 KB # of queries: 1933
7 Correct 34 ms 248 KB # of queries: 1934
8 Correct 43 ms 376 KB # of queries: 1826
9 Correct 38 ms 376 KB # of queries: 1920
10 Correct 21 ms 376 KB # of queries: 1076
11 Correct 5 ms 248 KB # of queries: 1
12 Correct 5 ms 248 KB # of queries: 3
13 Correct 5 ms 376 KB # of queries: 6
14 Correct 5 ms 248 KB # of queries: 9
15 Correct 6 ms 248 KB # of queries: 65
16 Correct 8 ms 376 KB # of queries: 159
17 Correct 359 ms 376 KB # of queries: 12754
18 Correct 326 ms 504 KB # of queries: 12528
19 Correct 330 ms 504 KB # of queries: 12443
20 Correct 316 ms 376 KB # of queries: 11640
21 Correct 288 ms 376 KB # of queries: 11103
22 Correct 322 ms 376 KB # of queries: 12490
23 Correct 363 ms 380 KB # of queries: 12667
24 Correct 116 ms 248 KB # of queries: 5886
25 Correct 372 ms 504 KB # of queries: 12374
26 Correct 342 ms 376 KB # of queries: 11502
27 Correct 111 ms 244 KB # of queries: 5690
28 Correct 324 ms 376 KB # of queries: 9977
29 Correct 303 ms 376 KB # of queries: 9966
30 Correct 306 ms 376 KB # of queries: 9977