Submission #27484

#	Time	Username	Problem	Language	Result	Execution time	Memory
27484		rondojim	ICC (CEOI16_icc)	C++14	61 / 100	186 ms	2220 KiB

icc

#include <stdio.h>
#include <vector>
#include <stdlib.h>
#include <algorithm>
#include "icc.h"

using namespace std;

const int MAXN = 105;

int a[MAXN], sza, b[MAXN], szb;
int t1[MAXN], szt1, t2[MAXN], szt2;
int p[MAXN];
vector<int> comp[MAXN], num;

int find(int u){
  return p[u] == u ? u : p[u] = find(p[u]);
}

void run(int N){
  for(int i=1; i<=N; ++i){
    num.push_back(i);
    comp[i].push_back(i);
    p[i] = i;
  }
  for(int k=1; k<N; ++k){
    while(true){
      random_shuffle(num.begin(), num.end());
      sza = szb = 0;
      for(int i=0; i<num.size(); ++i){
        if(!(i & 1))
          for(int x : comp[num[i]]) a[sza++] = x;
        else
          for(int x : comp[num[i]]) b[szb++] = x;
      }
      if(query(sza, szb, a, b)) break;
    }
    for(int r=1; r<=2; ++r){
      while(sza > 1){
        szt1 = szt2 = 0;
        for(int i=0; i<sza; ++i){
          if(!(i & 1)) t1[szt1++] = a[i];
          else t2[szt2++] = a[i];
        }
        if(query(szt1, szb, t1, b)){
          sza = szt1;
          for(int i=0; i<szt1; ++i) a[i] = t1[i];
        }
        else{
          sza = szt2;
          for(int i=0; i<szt2; ++i) a[i] = t2[i];
        }
      }
      int x = a[0];
      for(int i=0; i<szb; ++i) a[i] = b[i];
      b[0] = x;
      swap(sza, szb);
    }
    setRoad(a[0], b[0]);
    if(k == N - 1) break;
    a[0] = find(a[0]);
    b[0] = find(b[0]);
    for(int x : comp[b[0]]) comp[a[0]].push_back(x);
    comp[b[0]].clear();
    p[b[0]] = a[0];
    num.erase(find(num.begin(), num.end(), b[0]));
  }
}
    
            

Compilation message (stderr)

icc.cpp: In function 'void run(int)':
icc.cpp:30:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0; i<num.size(); ++i){
                     ^

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10