oj.uz

답안 #258382

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
258382 2020-08-05T21:00:55 Z kimbj0709 CEOI16_icc (CEOI16_icc) C++14
90 / 100
 145 ms 636 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(865685542);
    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<8;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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 512 KB Ok! 100 queries used.
2 Correct 7 ms 512 KB Ok! 109 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 512 KB Ok! 565 queries used.
2 Correct 45 ms 632 KB Ok! 674 queries used.
3 Correct 45 ms 512 KB Ok! 686 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 572 KB Ok! 1500 queries used.
2 Correct 142 ms 512 KB Ok! 1680 queries used.
3 Correct 139 ms 564 KB Ok! 1675 queries used.
4 Correct 134 ms 512 KB Ok! 1597 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 512 KB Ok! 1590 queries used.
2 Correct 142 ms 512 KB Ok! 1586 queries used.
3 Correct 145 ms 512 KB Ok! 1680 queries used.
4 Correct 140 ms 512 KB Ok! 1565 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 142 ms 512 KB Ok! 1670 queries used.
2 Correct 145 ms 512 KB Ok! 1680 queries used.
3 Correct 143 ms 512 KB Ok! 1680 queries used.
4 Correct 144 ms 636 KB Ok! 1683 queries used.
5 Correct 139 ms 572 KB Ok! 1559 queries used.
6 Correct 135 ms 564 KB Ok! 1586 queries used.

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 144 ms 512 KB Too many queries! 1680 out of 1625
2 Halted 0 ms 0 KB -