oj.uz

답안 #258374

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
258374 2020-08-05T20:54:42 Z kimbj0709 CEOI16_icc (CEOI16_icc) C++14
90 / 100
 176 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<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

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

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 512 KB Ok! 533 queries used.
2 Correct 45 ms 512 KB Ok! 678 queries used.
3 Correct 47 ms 512 KB Ok! 691 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 134 ms 512 KB Ok! 1488 queries used.
2 Correct 145 ms 512 KB Ok! 1689 queries used.
3 Correct 147 ms 560 KB Ok! 1671 queries used.
4 Correct 139 ms 632 KB Ok! 1583 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 147 ms 512 KB Ok! 1642 queries used.
2 Correct 139 ms 512 KB Ok! 1604 queries used.
3 Correct 147 ms 564 KB Ok! 1689 queries used.
4 Correct 135 ms 632 KB Ok! 1530 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 512 KB Ok! 1665 queries used.
2 Correct 151 ms 512 KB Ok! 1689 queries used.
3 Correct 151 ms 636 KB Ok! 1689 queries used.
4 Correct 176 ms 632 KB Ok! 1685 queries used.
5 Correct 137 ms 512 KB Ok! 1577 queries used.
6 Correct 144 ms 512 KB Ok! 1590 queries used.

Subtask #6
0 / 10.0

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