Submission #655006

#TimeUsernameProblemLanguageResultExecution timeMemory
655006Hiennoob123Library (JOI18_library)C++14
100 / 100
489 ms588 KiB
#include<bits/stdc++.h> #include "library.h" #define ll int //#define int long long #define ld long double #define cd complex<ld> #define pll pair<ll,ll> #define pii pair<int,int> #define pld pair<ld,ld> #define pb push_back #define mp make_pair #define fi first #define se second using namespace std ; ll n ; bool check[1005] ; ll deg[1005] ; vector<ll> T[1005] ; ll own[1005] ; vector<pll> Edge ; ll cnt_query= 0 ; ll ask(ll l , ll r , ll num) { vector<ll> que1(n , 0) , que2(n , 0) ; que1[num-1] = 1 ; for(int i = l ; i<= r ; i++) { que1[i-1] = que2[i-1] = 1 ; } cnt_query += 2 ; if(cnt_query>20000) { exit(69); } return (r-l+2-Query(que1)) - (r-l+1-Query(que2)) ; } ll ask(ll num) { vector<ll> que1(n , 0) , que2(n , 0) ; for(int i = 1 ; i<= n ; i++) { que1[i-1] = que2[i-1] = 1 ; } que2[num-1] = 0 ; cnt_query += 2 ; if(cnt_query>20000) { exit(69); } //cout << Query(que1) << " " << Query(que2) << "\n" ; return (n-Query(que1)) - (n-1-Query(que2)) ; } void dnc(ll l , ll r , ll num , ll sum) { if(sum==0) return ; if(r-l<1) { return ; } //cout << l << " " << r << " " << num << "\n" ; ll mid = ((l+r)>>1) ; ll this1 = ask(l , mid , num) ; if(this1>0) { if(l==mid) { Edge.push_back(mp(num , l)) ; deg[num]++ ; deg[l]++ ; } else { dnc(l , mid , num , this1) ; } } //cout << deg[num] << "\n" ; if(this1>=sum) return ; ll this2 = 1 ; if(this2>0) { if(r==mid+1) { Edge.push_back(mp(num , r)) ; deg[num]++ ; deg[l]++ ; } else { dnc(mid+1 , r , num , sum-this1) ; } } //deg[num] += this2 ; } bool val[1005] = {} ; void Solve(int m) { n = m ; if(n==1) { vector<ll> ans(1 , 1) ; Answer(ans) ; return ; } for(int i = 1 ; i< n-1 ; i++) { dnc(i+1 , n , i , ask(i+1 , n , i)) ; } if(n>1) { cnt_query += 1 ; if(cnt_query>20000) { exit(69) ; } vector<ll> que(n , 0); que[n-1] = que[n-2] = 1 ; //cout << Query(que) << "\n" ; if(Query(que)==1) Edge.push_back(mp(n-1 , n)) ; } for(int i = 0; i< Edge.size() ; i++) { //cout << Edge[i].fi << " " << Edge[i].se << "\n" ; T[Edge[i].fi].push_back(Edge[i].se) ; T[Edge[i].se].push_back(Edge[i].fi) ; } vector<ll> ans ; queue<ll> q ; for(int i = 1 ; i<= n ; i++) { if(T[i].size()==1) { q.push(i) ; break ; } } while(!q.empty()) { ll x = q.front(); q.pop() ; if(check[x]) continue ; check[x] = 1 ; ans.push_back(x) ; val[x] = 1 ; //cout << x << " " ; for(int i = 0; i< T[x].size() ; i++) { q.push(T[x][i]) ; } } //for(int i = 1 ; i<= n ; i++) if(ans[i-1]!=i) cout << i << "\n" ; //cout << cnt_query << "\n" ; //assert(ans.size()>=n) ; //cout << ans.size() << "-1" << endl; Answer(ans) ; }

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:120:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for(int i = 0; i< Edge.size() ; i++)
      |                    ~^~~~~~~~~~~~~
library.cpp:145:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |         for(int i = 0; i< T[x].size() ; i++)
      |                        ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...