Submission #205196

#	Time	Username	Problem	Language	Result	Execution time	Memory
205196		theStaticMind	Library (JOI18_library)	C++14	100 / 100	372 ms	504 KiB

library

#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 / 19
• Subtask 2: 81 / 81