Submission #994832

#TimeUsernameProblemLanguageResultExecution timeMemory
994832DzadzoLibrary (JOI18_library)C++14
0 / 100
19 ms2708 KiB
#include <bits/stdc++.h> #include "library.h" #define ll long long #define pb push_back #define S second #define F first #define pii pair<int,int> #define vi vector <int> #define vvi vector <vi> #define vvvi vector <vvi> #define vp vector <pii> #define vvp vector <vp> #define vb vector <bool> #define vvb vector <vb>; #define INF INT_MAX #define MOD 1000000007 #define MAXN 100000 using namespace std; map <vi,int >MP; /*int Query(const vi &v){ int cnt=0; for (int x:v)if (x)cnt++; if (cnt==1 || cnt==n)return 1; if (!MP[v]){ for (int x:v)cout<<x;cout<<"\n"; cin>>MP[v]; } return MP[v]; } void Answer(const vi &v){ cout<<"ANS"; for (int x:v)cout<<x<<" "; }*/ vvi arr; int N; int get(int l,int r,int idx1,int idx2){ vi M(N); for (int i=l;i<=r;i++){ for (int x:arr[i])M[x-1]=1; } if(idx1)M[idx1-1]=1; if(idx2)M[idx2-1]=1; int cnt=0; for (int x:M)if(x)cnt++; if (cnt==1 || cnt==N)return 1; if (MP[M])return MP[M]; return MP[M]=Query(M); } void Solve(int n){ N=n; arr.pb({1}); int res=1; for (int i=2;i<=n;i++){ int val=get(0,arr.size()-1,i,0); if (val==res+1){ arr.pb({i}); res++; }else if (val==res){ int ind=-1; for (int bit=9;bit>=0;bit--){ if (ind+(1<<bit)>=arr.size())continue; if (get(0,ind+(1<<bit),i,0)>get(0,ind+(1<<bit),0,0))ind+=(1<<bit); } ind++;//aq aris i if (get(0,-1,arr[ind][0],i)==1){ arr[ind].insert(arr[ind].begin(),i); }else{ arr[ind].pb(i); } }else if (val==res-1){ int ind=-1; for (int bit=9;bit>=0;bit--){ if (ind+(1<<bit)>=arr.size())continue; if (get(0,ind+(1<<bit),i,0)>get(0,ind+(1<<bit),0,0))ind+=(1<<bit); } ind++;//aq aris i vi newarr; if (get(0,-1,arr[ind][0],i)==1){ for (int x:arr[ind+1])newarr.pb(x); newarr.pb(i); for (int x:arr[ind])newarr.pb(x); }else{ for (int x:arr[ind])newarr.pb(x); newarr.pb(i); for (int x:arr[ind+1])newarr.pb(x); } vvi NEWarr; for (int i=0;i<arr.size();i++){ if (i==ind || i==ind+1)continue; NEWarr.pb(arr[i]); } NEWarr.pb(newarr); arr=NEWarr; res--; } } Answer(arr[0]); } /*signed main(){ int c; cin>>c; Solve(c); }*/

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:62:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     if (ind+(1<<bit)>=arr.size())continue;
      |         ~~~~~~~~~~~~^~~~~~~~~~~~
library.cpp:74:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     if (ind+(1<<bit)>=arr.size())continue;
      |         ~~~~~~~~~~~~^~~~~~~~~~~~
library.cpp:89:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |    for (int i=0;i<arr.size();i++){
      |                 ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...