Submission #966701

#	Time	Username	Problem	Language	Result	Execution time	Memory
966701		berr	ICC (CEOI16_icc)	C++17	0 / 100	1 ms	604 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
vector<int> vis(101);


int que(vector<int> a, vector<int> b){
    int x[a.size()], y[b.size()];

    int siz_a = a.size(), siz_b=b.size();

    for(int i=0; i<siz_a; i++){
        x[i] = a[i];
    }

    for(int i=0; i<siz_b; i++){
        y[i] = b[i];
    }

    return query(siz_a, siz_b, x, y);
}

void coz(vector<int> a, vector<int> b){
     while(a.size()>1){
        vector<int> pf;
        for(int i=0; i<a.size()/2; i++){
            pf.push_back(a[i]);
        }

        if(que(pf, b)){
            a= pf;
        }
        else{
            pf.clear();
            for(int i=a.size()/2; i<a.size(); i++){
                pf.push_back(a[i]);
            }

            a=pf;
        }
    }

    while(b.size()>1){
        vector<int> pf;
        for(int i=0; i<b.size()/2; i++){
            pf.push_back(b[i]);
        }

        if(que(a, b)){
            b= pf;
        }
        else{
            pf.clear();
            for(int i=b.size()/2; i<b.size(); i++){
                pf.push_back(b[i]);
            }

            b=pf;
        }

    }
    vis[a[0]]=1; vis[b[0]]=1;

    setRoad(a[0], b[0]);
}


void run(int n){
    for(int i=0; i<n; i++) vis[i]=0;

    for(int i=0; i<n-1; i++){

        vector<int> unvisited, visited;
        
        for(int l=1; l<=n; l++){
            if(vis[l]) visited.push_back(l);
            else unvisited.push_back(l);
        }
        if(visited.size()==0 || !que(unvisited, visited)){
            vector<int> all = unvisited;
            vector<int> a, b;
            while(all.size() < 2){
                a.clear(); b.clear();
                
                int size_all = all.size();
                for(int i=0; i<size_all; i++){
                    if(i<size_all/2) a.push_back(all[i]);
                    else b.push_back(all[i]);
                }

                if(que(a, b)){
                    break;
                }
                else{
                    vector<vector<int>> aa;
                    vector<vector<int>> bb;

                    while(1){
                        vector<vector<int>> new_aa;
                        vector<vector<int>> new_bb;
                        int sa=0, sb=0;
                        for(auto i: aa){    
                            vector<int> a, b;

                            for(int l=0; l<i.size(); l++){
                                if(l<i.size()/2){
                                    a.push_back(i[l]);
                                    sa++;
                                }
                                else if(l==i.size()/2 && i.size()%2){
                                    if(sa+1 <= sb+i.size()/2){
                                        a.push_back(i[l]);
                                        sa++;
                                    }
                                    else{
                                        b.push_back(i[l]);
                                        sb++;
                                    }
                                }
                                else{
                                    b.push_back(i[l]);
                                    sb++;
                                }
                            }

                            if(a.size()==0||b.size()==0) continue;
                            else{
                                new_aa.push_back(a);
                                new_bb.push_back(b);
                            }
                        }

                        for(auto i: bb){    
                            vector<int> a, b;

                            for(int l=0; l<i.size(); l++){
                                if(l<i.size()/2){
                                    a.push_back(i[l]);
                                    sa++;
                                }
                                else if(l==i.size()/2 && i.size()%2){
                                    if(sa+1 <= sb+i.size()/2){
                                        a.push_back(i[l]);
                                        sa++;
                                    }
                                    else{
                                        b.push_back(i[l]);
                                        sb++;
                                    }
                                }
                                else{
                                    b.push_back(i[l]);
                                    sb++;
                                }
                            }

                            if(a.size()==0||b.size()==0) continue;
                            else{
                                new_aa.push_back(a);
                                new_bb.push_back(b);
                            }
                        }

                        vector<int> ca, cb;

                        for(auto i: new_aa)
                            for(auto l: i) ca.push_back(l);
                        
                        for(auto i: new_bb)
                            for(auto l: i)
                                cb.push_back(l);

                        if(que(ca, cb)){
                            int s=-1;
                            
                            auto check=[&](int val){
                                vector<int> pf, fp;

                                for(int i=0; i<=val; i++){
                                    for(auto l: new_aa[i]){
                                        pf.push_back(l);
                                    }
                                    for(auto l: new_bb[i]){
                                        fp.push_back(l);
                                    }
                                }

                                if(que(pf, fp)) return 1;
                                return 0;
                            };

                            for(int j=6; j>=0; j--){
                                int tmp = s+(1<<j);
                                if(tmp <new_aa.size()-1){
                                    if(check(tmp)) continue;
                                    s = tmp;
                                }
                            }

                            a=new_aa[s+1]; b=new_bb[s+1];
                            break;
                        }
                        else{
                            aa=new_aa; bb=new_bb;
                        }

                    }

                   
                }


            }

            coz(a, b);

        }
        else{
            coz(visited, unvisited);
        }
    }

}

Compilation message (stderr)

icc.cpp: In function 'void coz(std::vector<int>, std::vector<int>)':
icc.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int i=0; i<a.size()/2; i++){
      |                      ~^~~~~~~~~~~
icc.cpp:35:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             for(int i=a.size()/2; i<a.size(); i++){
      |                                   ~^~~~~~~~~
icc.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(int i=0; i<b.size()/2; i++){
      |                      ~^~~~~~~~~~~
icc.cpp:54:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             for(int i=b.size()/2; i<b.size(); i++){
      |                                   ~^~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:105:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |                             for(int l=0; l<i.size(); l++){
      |                                          ~^~~~~~~~~
icc.cpp:106:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |                                 if(l<i.size()/2){
      |                                    ~^~~~~~~~~~~
icc.cpp:110:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |                                 else if(l==i.size()/2 && i.size()%2){
      |                                         ~^~~~~~~~~~~~
icc.cpp:111:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |                                     if(sa+1 <= sb+i.size()/2){
      |                                        ~~~~~^~~~~~~~~~~~~~~~
icc.cpp:136:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |                             for(int l=0; l<i.size(); l++){
      |                                          ~^~~~~~~~~
icc.cpp:137:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |                                 if(l<i.size()/2){
      |                                    ~^~~~~~~~~~~
icc.cpp:141:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |                                 else if(l==i.size()/2 && i.size()%2){
      |                                         ~^~~~~~~~~~~~
icc.cpp:142:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |                                     if(sa+1 <= sb+i.size()/2){
      |                                        ~~~~~^~~~~~~~~~~~~~~~
icc.cpp:194:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |                                 if(tmp <new_aa.size()-1){
      |                                    ~~~~^~~~~~~~~~~~~~~~

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