Submission #127624

#TimeUsernameProblemLanguageResultExecution timeMemory
127624VardanyanICC (CEOI16_icc)C++14
90 / 100
161 ms732 KiB
#include <bits/stdc++.h> #include "icc.h" using namespace std; vector<int> g[101]; int bt[101][100]; /* int query(int n,int m,int* a,int* b){ cout<<n<<" "<<m<<endl; for(int i = 0;i<n;i++) cout<<a[i]<<" "; cout<<endl; for(int i = 0;i<m;i++) cout<<b[i]<<" "; cout<<endl; int x; cin>>x; return x; }*/ int a[101]; int b[101]; void run(int N){ int n = N; for(int i = 1;i<=n;i++) g[i].push_back(i); vector<int> v; for(int i = 1;i<=n;i++) v.push_back(i); int k = n-1; while(k--){ for(int i = 0;i<v.size();i++){ for(int j = 0;j<20;j++){ bt[i][j] = (v[i]>>j)&1; } } vector<int> f,s; for(int i = 0;;i++){ f.clear(); s.clear(); for(int j = 0;j<v.size();j++){ if(bt[j][i]) f.push_back(v[j]); else s.push_back(v[j]); } if(f.size() == 0 || s.size() == 0) continue; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); int ps1 = 0; int ps2 = 0; for(int j = 0;j<f.size();j++){ // a[j] = f[j]; for(int jj = 0;jj<g[f[j]].size();jj++){ a[ps1++] = g[f[j]][jj]; } } for(int j = 0;j<s.size();j++){ // b[j] = s[j]; for(int jj = 0;jj<g[s[j]].size();jj++){ b[ps2++] = g[s[j]][jj]; } } int x; x = query(ps1,ps2,a,b); if(x) break; } int l = 0,r = f.size()-1; int ans; int ps1 = 0; int ps2 = 0; for(int j = 0;j<f.size();j++){ for(int jj = 0;jj<g[f[j]].size();jj++){ a[ps1++] = g[f[j]][jj]; } } for(int j = 0;j<s.size();j++){ for(int jj = 0;jj<g[s[j]].size();jj++){ b[ps2++] = g[s[j]][jj]; } } f.clear(); s.clear(); for(int j = 0;j<ps1;j++) f.push_back(a[j]); for(int j = 0;j<ps2;j++) s.push_back(b[j]); l = 0,r = f.size()-1; // ans = 0; for(int j = 0;j<s.size();j++) b[j] = s[j]; while(l<=r){ /*if(l == r){ break; }*/ int mid = (l+r)/2; memset(a,0,sizeof(a)); // memset(b,0,sizeof(b)); int ps = 0; for(int j = l;j<=mid;j++){ a[ps] = f[j]; ps++; } int x; x = query(mid-l+1,s.size(),a,b); if(x){ ans = mid; r = mid-1; } else l = mid+1; } l = 0,r = s.size()-1; // ans2; int ans2; memset(a,0,sizeof(a)); for(int j = 0;j<f.size();j++) a[j] = f[j]; while(l<=r){ /* if(l == r){ break; }*/ int mid = (l+r)/2; memset(b,0,sizeof(b)); int ps = 0; for(int j = l;j<=mid;j++){ b[ps] = s[j]; ps++; } int x; x = query(f.size(),mid-l+1,a,b); if(x){ ans2 = mid; r = mid-1; } else l = mid+1; } ans = f[ans]; ans2 = s[ans2]; setRoad(ans,ans2); // cout<<"found "<<ans<<" "<<ans2<<endl; int comp1,comp2; for(int j = 1;j<=n;j++){ for(int jj = 0;jj<g[j].size();jj++){ if(g[j][jj] == ans){ comp1 = j; break; } } } for(int j = 1;j<=n;j++){ for(int jj = 0;jj<g[j].size();jj++){ if(g[j][jj] == ans2){ comp2 = j; break; } } } for(int j = 0;j<g[comp2].size();j++){ g[comp1].push_back(g[comp2][j]); } g[comp2].clear(); v.clear(); for(int j = 1;j<=n;j++){ if(g[j].size()) v.push_back(j); } } } /* int main() { ios_base::sync_with_stdio(false); run(4); return 0; }*/

Compilation message (stderr)

icc.cpp: In function 'void run(int)':
icc.cpp:26:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i<v.size();i++){
                       ~^~~~~~~~~
icc.cpp:35:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0;j<v.size();j++){
                           ~^~~~~~~~~
icc.cpp:44:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
            for(int j = 0;j<f.size();j++){
                          ~^~~~~~~~~
icc.cpp:46:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int jj = 0;jj<g[f[j]].size();jj++){
                                ~~^~~~~~~~~~~~~~~
icc.cpp:50:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
            for(int j = 0;j<s.size();j++){
                          ~^~~~~~~~~
icc.cpp:52:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int jj = 0;jj<g[s[j]].size();jj++){
                                ~~^~~~~~~~~~~~~~~
icc.cpp:64:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j<f.size();j++){
                       ~^~~~~~~~~
icc.cpp:65:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int jj = 0;jj<g[f[j]].size();jj++){
                            ~~^~~~~~~~~~~~~~~
icc.cpp:69:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j<s.size();j++){
                       ~^~~~~~~~~
icc.cpp:70:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int jj = 0;jj<g[s[j]].size();jj++){
                            ~~^~~~~~~~~~~~~~~
icc.cpp:81:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j<s.size();j++) b[j] = s[j];
                       ~^~~~~~~~~
icc.cpp:106:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j<f.size();j++) a[j] = f[j];
                       ~^~~~~~~~~
icc.cpp:132:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int jj = 0;jj<g[j].size();jj++){
                            ~~^~~~~~~~~~~~
icc.cpp:140:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int jj = 0;jj<g[j].size();jj++){
                            ~~^~~~~~~~~~~~
icc.cpp:147:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j<g[comp2].size();j++){
                       ~^~~~~~~~~~~~~~~~
icc.cpp:130:19: warning: 'comp2' may be used uninitialized in this function [-Wmaybe-uninitialized]
         int comp1,comp2;
                   ^~~~~
icc.cpp:127:22: warning: 'ans2' may be used uninitialized in this function [-Wmaybe-uninitialized]
         ans2 = s[ans2];
                      ^
icc.cpp:126:20: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
         ans = f[ans];
                    ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...