oj.uz

Submission #27484

# Submission time Handle Problem Language Result Execution time Memory
27484 2017-07-13T07:21:53 Z rondojim ICC (CEOI16_icc) C++14
61 / 100
 186 ms 2220 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2088 KB Ok! 108 queries used.
2 Correct 6 ms 2084 KB Ok! 106 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2088 KB Ok! 520 queries used.
2 Correct 59 ms 2092 KB Ok! 820 queries used.
3 Correct 53 ms 2084 KB Ok! 774 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 2216 KB Ok! 1457 queries used.
2 Correct 186 ms 2084 KB Ok! 2098 queries used.
3 Correct 126 ms 2216 KB Ok! 1485 queries used.
4 Correct 146 ms 2216 KB Ok! 1697 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 2216 KB Ok! 1568 queries used.
2 Correct 136 ms 2216 KB Ok! 1551 queries used.
3 Correct 166 ms 2220 KB Ok! 1847 queries used.
4 Correct 136 ms 2220 KB Ok! 1534 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 156 ms 2216 KB Too many queries! 1814 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 2216 KB Too many queries! 1838 out of 1625
2 Halted 0 ms 0 KB -