Submission #127624

#	Time	Username	Problem	Language	Result	Execution time	Memory
127624		Vardanyan	ICC (CEOI16_icc)	C++14	90 / 100	161 ms	732 KiB

icc

#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];
                    ^

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 0 / 10