oj.uz

Submission #135389

# Submission time Handle Problem Language Result Execution time Memory
135389 2019-07-24T04:38:57 Z dragonslayerit ICC (CEOI16_icc) C++14
0 / 100
 6 ms 888 KB 
#include "icc.h"

#include <cstdio>
#include <vector>
#include <cassert>

bool query(std::vector<int> a,std::vector<int> b){
  for(int& x:a) x++;
  for(int& x:b) x++;
  return query(a.size(),b.size(),a.data(),b.data());
}

template<class Iterator>
bool query(Iterator b1,Iterator e1,Iterator b2,Iterator e2){
  return query(std::vector<int>(b1,e1),std::vector<int>(b2,e2));
}

int find(int a,std::vector<int>& uf){
  while(a!=uf[a]){
    a=uf[a]=uf[uf[a]];
  }
  return a;
}

void merge(int a,int b,std::vector<int>& uf){
  uf[find(a,uf)]=find(b,uf);
}

template<class Iterator>
std::pair<int,int> locate(Iterator b1,Iterator e1,Iterator b2,Iterator e2){
  while(e1-b1!=1){
    Iterator m1=b1+(e1-b1)/2;
    if(query(b1,m1,b2,e2)){
      e1=m1;
    }else{
      b1=m1;
    }
  }
  while(e2-b2!=1){
    Iterator m2=b2+(e2-b2)/2;
    if(query(b1,e1,b2,m2)){
      e2=m2;
    }else{
      b2=m2;
    }
  }
  return std::pair<int,int>(*b1,*b2);
}

template<class Iterator>
std::pair<int,int> locate(Iterator begin,Iterator end){
  for(int k=0;(1<<k)<=end-begin;k++){
    std::vector<int> as,bs;
    for(int i=0;i<end-begin;i++){
      if(i&(1<<k)){
	as.push_back(i);
      }else{
	bs.push_back(i);
      }
    }
    if(query(as,bs)){
      return locate(as.begin(),as.end(),bs.begin(),bs.end());
    }
  }
  assert(0);
}

void solve(std::vector<int>& uf){
  std::vector<int> reps;
  for(int i=0;i<uf.size();i++){
    if(i==uf[i]){
      reps.push_back(i);
    }
  }
  std::pair<int,int> pair=locate(reps.begin(),reps.end());
  std::vector<int> as,bs;
  for(int i=0;i<uf.size();i++){
    if(find(i,uf)==find(pair.first,uf)){
      as.push_back(i);
    }
    if(find(i,uf)==find(pair.second,uf)){
      bs.push_back(i);
    }
  }
  pair=locate(as.begin(),as.end(),bs.begin(),bs.end());
  setRoad(pair.first+1,pair.second+1);
  merge(pair.first,pair.second,uf);
}

void run(int N){
  std::vector<int> uf(N);
  for(int i=0;i<N;i++){
    uf[i]=i;
  }
  for(int i=0;i<N-1;i++){
    solve(uf);
  }
}

Compilation message

icc.cpp: In function 'void solve(std::vector<int>&)':
icc.cpp:70:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<uf.size();i++){
               ~^~~~~~~~~~
icc.cpp:77:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<uf.size();i++){
               ~^~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 508 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 504 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 504 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 504 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -