Submission #820510

#TimeUsernameProblemLanguageResultExecution timeMemory
820510Faisal_SaqibLibrary (JOI18_library)C++17
19 / 100
219 ms656 KiB
#include <bits/stdc++.h> #include <cstdio> #include <vector> #include <cstdlib> #include <cstring> #include "library.h" using namespace std; // void Solve(int N); int par[10000]; int ans1[10000]; bool vis[10000]; int n; map<int,vector<int>> ma; int query(vector<int>& a,bool p=0) { // cout<<"for "; // for(auto i:a) // { // cout<<i<<' '; // } // cout<<endl; vector<int> que(n); for(auto i:a) { que[i-1]=1; } return Query(que); } int get(int x) { if(x==par[x]) { return x; } return par[x]=get(par[x]); } void join(int a,int b) { a=get(a); b=get(b); par[a]=b; } int check(vector<int> a,int b) { // cout<<"reason "<<b<<endl; a.push_back(b); int x=query(a,1); // cout<<"answer "<<x<<endl; if(x==a.size()) { return 0; } else if(x==(a.size()-1)) { return 1; } else { return 2; } } void find(vector<int> a,int x,int mn) { if(mn==0 or a.size()==0) { return; } if(a.size()==1) { // cout<<"Book "<<x<<' '<<" adj to ";; for(int i=0;i<1;i++) { // cout<<a[i]<<' '; ma[a[i]].push_back(x); ma[x].push_back(a[i]); } // cout<<endl; return; } int mid=(a.size()/2); vector<int> fh,sh; for(int i=0;i<a.size();i++) { if(i<mid) { fh.push_back(a[i]); } else { sh.push_back(a[i]); } } find(fh,x,check(fh,x)); find(sh,x,check(sh,x)); } int cur=1; void dfs(int x) { vis[x]=1; ans1[cur]=x; // cout<<x<<' '<<cur<<endl; cur++; for(auto y:ma[x]) { // cout<<"adj "<<y<<' '<<x<<endl; if(!vis[y]) { dfs(y); } } } void Solve(int opas) { n=opas; // cout<<"Hello"<<endl; vector<int> h; h.push_back(1); for(int i=2;i<=n;i++) { h.push_back(i); int x=query(h); // cout<<"Now"<<endl; if(x==h.size()) { // cout<<i<<' '<<"Dif"<<endl; } else if(x==(h.size()-1)) { h.pop_back(); find(h,i,1); h.push_back(i); } else { h.pop_back(); find(h,i,2); h.push_back(i); } } vector<int> ans(n); for(int i=1;i<=n;i++) { if(ma[i].size()==1 and !vis[i]) { dfs(i); } } for(int i=1;i<=n;i++) { if(!vis[i]) { ans1[cur]=i; cur++; } } // cout<<"Hello"<<endl; for(int i=1;i<=n;i++) { // cout<<ans1[i]<<' '; ans[i-1]=ans1[i]; } // cout<<endl; Answer(ans); }

Compilation message (stderr)

library.cpp: In function 'int check(std::vector<int>, int)':
library.cpp:49:6: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  if(x==a.size())
      |     ~^~~~~~~~~~
library.cpp:53:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  else if(x==(a.size()-1))
      |          ~^~~~~~~~~~~~~~
library.cpp: In function 'void find(std::vector<int>, int, int)':
library.cpp:82:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  for(int i=0;i<a.size();i++)
      |              ~^~~~~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:123:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |   if(x==h.size())
      |      ~^~~~~~~~~~
library.cpp:127:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |   else if(x==(h.size()-1))
      |           ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...