Submission #255639

#	Time	Username	Problem	Language	Result	Execution time	Memory
255639		kimbj0709	ICC (CEOI16_icc)	C++14	18 / 100	424 ms	576 KiB

icc

#include<bits/stdc++.h>
#include "icc.h"
using namespace std;
//#define int long long
vector<int> color(105);
vector<vector<int> > comp(105);
int q(vector<int> &a,vector<int> &b){
    if(a.size()==0||b.size()==0){
        return 0;
    }
    int aa[(int)a.size()];
    int bb[(int)b.size()];
    for(int i=0;i<(int)a.size();i++){
        aa[i] = a[i];
    }
    for(int i=0;i<(int)b.size();i++){
        bb[i] = b[i];
    }
    /*for(auto k:a){
        cout << k << " ";
    }
    cout << endl;
    for(auto k:b){
        cout << k << " ";
    }
    cout << endl;
    int input;
    cin >> input;
    return input;*/
    return query(a.size(),b.size(),aa,bb);

}
int qcomp(vector<int> &a,vector<int> &b){
    vector<int> temp1,temp2;
    for(auto k:a){
        for(auto j:comp[k]){
            temp1.push_back(j);
        }
    }
    for(auto k:b){
        for(auto j:comp[k]){
            temp2.push_back(j);
        }
    }
    return q(temp1,temp2);
}
void road(int a,int b){
    //cout << a << " " << b << "__" << endl;
    setRoad(min(a,b),max(a,b));
}
void merge(int a,int b){
    for(auto k:comp[color[b]]){
        comp[color[a]].push_back(k);
    }
    int change = color[b];
    for(int i=1;i<color.size();i++){
        if(color[i]==change){
            color[i] = color[a];
        }
    }
    comp[change].clear();
}
void binarysearch(vector<int> left,vector<int> right){
    vector<int> temp1;
    vector<int> temp2;
    for(auto k:left){
        for(auto j:comp[k]){
            temp1.push_back(j);
        }
    }
    for(auto k:right){
        for(auto j:comp[k]){
            temp2.push_back(j);
        }
    }
    left = temp1;
    right = temp2;
    while(left.size()!=1){
        vector<int> curr;
        for(int i=0;i<(left.size()+1)/2;i++){
            curr.push_back(left[i]);
        }
        vector<int> curr2;
        for(int i=(left.size()+1)/2;i<left.size();i++){
            curr2.push_back(left[i]);
        }
        if(q(curr,right)==1){
            left = curr;
        }
        else{
            left = curr2;
        }
    }
    swap(left,right);
    while(left.size()!=1){
        vector<int> curr;
        for(int i=0;i<(left.size()+1)/2;i++){
            curr.push_back(left[i]);
        }
        vector<int> curr2;
        for(int i=(left.size()+1)/2;i<left.size();i++){
            curr2.push_back(left[i]);
        }
        if(q(curr,right)==1){
            left = curr;
        }
        else{
            left = curr2;
        }
    }
    assert(left.size()==1&&right.size()==1);
    road(left[0],right[0]);
    merge(left[0],right[0]);
}
int rec(vector<int> a){
    vector<int> left,right;
    for(int i=0;i<(a.size()+1)/2;i++){
        left.push_back(a[i]);
    }
    for(int i=(a.size()+1)/2;i<a.size();i++){
        right.push_back(a[i]);
    }
    if(left.size()==0||right.size()==0){
        return 0;
    }
    if(qcomp(left,right)==0){
        if(rec(left)==1){
            return 1;
        }
        else{
          if(rec(right)==1){
              return 1;
          }
        }
    }
    else{
        binarysearch(left,right);
        return 1;
    }
    return 0;
}
void run(int n){
    for(int i=0;i<color.size();i++){
        comp[i].clear();
        comp[i].push_back(i);
        color[i] = i;
    }
    vector<int> current;
    vector<int> alr;
    for(int i=1;i<=n-1;i++){
        //cout << "YES" << endl;
        for(int j=1;j<=n;j++){
            if(comp[j].size()!=0){
                current.push_back(j);
            }
        }
        rec(current);
        current.clear();
    }
}

Compilation message (stderr)

icc.cpp: In function 'void merge(int, int)':
icc.cpp:56:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<color.size();i++){
                 ~^~~~~~~~~~~~~
icc.cpp: In function 'void binarysearch(std::vector<int>, std::vector<int>)':
icc.cpp:80:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<(left.size()+1)/2;i++){
                     ~^~~~~~~~~~~~~~~~~~
icc.cpp:84:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=(left.size()+1)/2;i<left.size();i++){
                                     ~^~~~~~~~~~~~
icc.cpp:97:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<(left.size()+1)/2;i++){
                     ~^~~~~~~~~~~~~~~~~~
icc.cpp:101:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=(left.size()+1)/2;i<left.size();i++){
                                     ~^~~~~~~~~~~~
icc.cpp: In function 'int rec(std::vector<int>)':
icc.cpp:117:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<(a.size()+1)/2;i++){
                 ~^~~~~~~~~~~~~~~
icc.cpp:120:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=(a.size()+1)/2;i<a.size();i++){
                              ~^~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:143:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<color.size();i++){
                 ~^~~~~~~~~~~~~

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