oj.uz

Submission #258364

# Submission time Handle Problem Language Result Execution time Memory
258364 2020-08-05T20:36:31 Z kimbj0709 ICC (CEOI16_icc) C++14
0 / 100
 78 ms 564 KB 
#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];
    }
    return query(a.size(),b.size(),aa,bb);
 
}
void road(int a,int b){
    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]);
}
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> rands;
    for(int i=0;i<10;i++){
      rands.push_back(i);
    }
    for(int i=0;i<n-1;i++){
      vector<int> current;
      for(int j=1;j<=n;j++){
        if(comp[j].size()!=0){
          current.push_back(j);
        }
      }
      random_shuffle(rands.begin(),rands.end());
      for(int ii=0;ii<rands.size();ii++){
        vector<int> a,b;
        for(int j=0;j<current.size();j++){
          if((1<<rands[ii])&j){
            a.push_back(current[j]);
          }
          else{
            b.push_back(current[j]);
          }
        }
        if(q(a,b)==1){
          binarysearch(a,b);
          goto cont;
        }
      }
      cont : ;
    }
}

Compilation message

icc.cpp: In function 'void merge(int, int)':
icc.cpp:30: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:54:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<(left.size()+1)/2;i++){
                     ~^~~~~~~~~~~~~~~~~~
icc.cpp:58:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=(left.size()+1)/2;i<left.size();i++){
                                     ~^~~~~~~~~~~~
icc.cpp:71:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<(left.size()+1)/2;i++){
                     ~^~~~~~~~~~~~~~~~~~
icc.cpp:75: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 'void run(int)':
icc.cpp:90:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<color.size();i++){
                 ~^~~~~~~~~~~~~
icc.cpp:107:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int ii=0;ii<rands.size();ii++){
                    ~~^~~~~~~~~~~~~
icc.cpp:109:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<current.size();j++){
                     ~^~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 512 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 512 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 512 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 564 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 512 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 512 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -