Submission #827838

#TimeUsernameProblemLanguageResultExecution timeMemory
827838MohamedAhmed04Library (JOI18_library)C++14
100 / 100
217 ms592 KiB
#include <bits/stdc++.h> #include "library.h" using namespace std; const int MAX = 1000 + 10 ; int n ; vector<int>v[MAX] ; int taken[MAX] ; bool check(int l , int r) { vector<int>vq(n , 0) ; int cnt = r-l+1 ; for(int i = l ; i <= r ; ++i) { vq[i] = 1 ; for(auto &j : v[i]) cnt -= (j > i && j <= r) ; } return (Query(vq) < cnt) ; } void Find_Adjacent(int idx , int cnt) { for(int i = 0 ; i < cnt ; ++i) { int l = 0 , r = idx ; int idx2 = -1 ; while(l <= r) { int mid = (l + r) >> 1 ; if(check(mid , idx)) idx2 = mid , l = mid+1 ; else r = mid-1 ; } v[idx].push_back(idx2) , v[idx2].push_back(idx) ; } } void Solve(int N) { n = N ; if(n == 1) { Answer({1}) ; return ; } vector<int>vq(n , 0) ; int cur = 0 ; for(int i = 0 ; i < n ; ++i) { ++cur ; vq[i] = 1 ; int x = Query(vq) ; Find_Adjacent(i , cur - x) ; cur = x ; } vector<int>ans ; int x = -1 ; for(int i = 0 ; i < n ; ++i) { if(v[i].size() == 1) { x = i ; break ; } } while(ans.size() < n) { ans.push_back(x+1) ; taken[x] = 1 ; for(auto &i : v[x]) { if(!taken[i]) { x = i ; break ; } } } Answer(ans) ; }

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:72:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |  while(ans.size() < n)
      |        ~~~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...