oj.uz

Submission #258378

# Submission time Handle Problem Language Result Execution time Memory
258378 2020-08-05T20:58:52 Z kimbj0709 ICC (CEOI16_icc) C++14
90 / 100
 162 ms 632 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);
}
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){
    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,curr2;
        for(int i=0;i<left.size();i++){
          if(i%2==1){
            curr.push_back(left[i]);
          }
          else{
            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,curr2;
        for(int i=0;i<left.size();i++){
          if(i%2==1){
            curr.push_back(left[i]);
          }
          else{
            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){
    srand(865542);
    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(qcomp(a,b)==1){
          binarysearch(a,b);
          goto cont;
        }
      }
      assert(1==0);
      cont : ;
    }
}

Compilation message

icc.cpp: In function 'void merge(int, int)':
icc.cpp:43: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:67:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<left.size();i++){
                     ~^~~~~~~~~~~~
icc.cpp:85:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<left.size();i++){
                     ~^~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:106:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<color.size();i++){
                 ~^~~~~~~~~~~~~
icc.cpp:123:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int ii=0;ii<rands.size();ii++){
                    ~~^~~~~~~~~~~~~
icc.cpp:125:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<current.size();j++){
                     ~^~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Ok! 99 queries used.
2 Correct 6 ms 512 KB Ok! 102 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 512 KB Ok! 552 queries used.
2 Correct 46 ms 632 KB Ok! 678 queries used.
3 Correct 45 ms 512 KB Ok! 671 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 512 KB Ok! 1506 queries used.
2 Correct 156 ms 512 KB Ok! 1681 queries used.
3 Correct 143 ms 632 KB Ok! 1664 queries used.
4 Correct 137 ms 512 KB Ok! 1594 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 568 KB Ok! 1620 queries used.
2 Correct 148 ms 632 KB Ok! 1630 queries used.
3 Correct 162 ms 568 KB Ok! 1681 queries used.
4 Correct 130 ms 512 KB Ok! 1523 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 512 KB Ok! 1669 queries used.
2 Correct 145 ms 512 KB Ok! 1681 queries used.
3 Correct 145 ms 512 KB Ok! 1681 queries used.
4 Correct 148 ms 576 KB Ok! 1691 queries used.
5 Correct 140 ms 512 KB Ok! 1569 queries used.
6 Correct 137 ms 512 KB Ok! 1587 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 144 ms 512 KB Too many queries! 1681 out of 1625
2 Halted 0 ms 0 KB -