oj.uz

Submission #75723

# Submission time Handle Problem Language Result Execution time Memory
75723 2018-09-10T19:39:48 Z KieranHorgan Mechanical Doll (IOI18_doll) C++17
100 / 100
 186 ms 16792 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> A, X, Y, C;
int dep[200];
int nextSwitch = -1;
vector<int> AdjList[200005];

int globalCurSwitch;

int recurseThroughTree(vector<int> b) {
  if(b.size() == 1) return b[0];
  int curSwitch = nextSwitch--;

  vector<int> a;

  a.clear();
  int nextDummies = 0;
  for(int i = 0; i < b.size(); i+=2) {
    if(b[i] == globalCurSwitch) nextDummies++;
    a.push_back(b[i]);
  }
  int l;
  if(nextDummies == a.size()) {
    l = globalCurSwitch;
  } else {
    l = recurseThroughTree(a);
  }

  a.clear();
  for(int i = 1; i < b.size(); i+=2) {
    if(b[i] == globalCurSwitch) nextDummies++;
    a.push_back(b[i]);
  }
  int r = recurseThroughTree(a);

  if(X.size() <= abs(curSwitch)-1) X.resize(abs(curSwitch)), Y.resize(abs(curSwitch));
  X[abs(curSwitch)-1] = l;
  Y[abs(curSwitch)-1] = r;

  return curSwitch;
}

int rev(int x, int n) {
  n = __builtin_ctz(n);
  int res = 0;
  for(int i = 0; i < n; i++)
    if(x & (1<<i))
      res |= 1<<(n-1-i);
  // cerr << n << ": " << x << " -> " << res << endl;
  return res;
}

void buildTree(int curTrigger, int curSwitch) {
  globalCurSwitch = curSwitch;
  int x = AdjList[curTrigger].size();
  int dummies = 0;
  while(__builtin_popcount(x+dummies) != 1)
    dummies++;

  vector<int> b = AdjList[curTrigger];

  vector<int> a;
  int i, j;
  for(i = 0, j = 0; j < b.size() + dummies; j++) {
    if(i >= b.size() || rev(j, b.size()+dummies) < dummies) a.push_back(globalCurSwitch);
    else a.push_back(b[i++]);
  }
  // for(auto x: a)
    // cerr << x << " ";
  // cerr << endl;
  // for(auto x: b)
    // cerr << x << " ";
  // cerr << endl;
  // cerr << endl;

  vector<int> pos, posCop;

  b = a;

  a.clear();
  int nextDummies = 0;
  for(int i = 0; i < b.size(); i+=2) {
    a.push_back(b[i]);
  }
  int l = recurseThroughTree(a);

  a.clear();
  nextDummies = 0;
  for(int i = 1; i < b.size(); i+=2) {
    a.push_back(b[i]);
  }
  int r = recurseThroughTree(a);
  a.clear();

  if(X.size() <= abs(curSwitch)-1) X.resize(abs(curSwitch)), Y.resize(abs(curSwitch));
  X[abs(curSwitch)-1] = l;
  Y[abs(curSwitch)-1] = r;
}

void create_circuit(int M, vector<int> A_) {
  A = A_;
  int N = A.size();

  for(int i = 1; i < A.size(); i++)
    AdjList[A[0]].push_back(A[i]);
  AdjList[A[0]].push_back(0);  

  C.assign(M+1, -1);
  C[0] = A[0];
  nextSwitch--;
  if(N == 1)
    C[1] = 0;
  else
    buildTree(A[0], C[A[0]]);

  double score;
  int S = X.size();
  // cerr << S << " " << N+log2(N) << endl;
  if(S <= N + log2(N)) score = 1;
  else if(S <= 2*N) score = 0.5 + 0.4*((2*N - S)/(N-log2(N)))*((2*N - S)/(N-log2(N)));
  else score = 0;
  score *= 100;

  // cout << "Score: " << setprecision(7) << fixed << score << "\t"  ;
  answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'int recurseThroughTree(std::vector<int>)':
doll.cpp:20:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   for(int i = 0; i < b.size(); i+=2) {
      |                  ~~^~~~~~~~~~
doll.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   if(nextDummies == a.size()) {
      |      ~~~~~~~~~~~~^~~~~~~~~~~
doll.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int i = 1; i < b.size(); i+=2) {
      |                  ~~^~~~~~~~~~
doll.cpp:38:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |   if(X.size() <= abs(curSwitch)-1) X.resize(abs(curSwitch)), Y.resize(abs(curSwitch));
      |      ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
doll.cpp: In function 'void buildTree(int, int)':
doll.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for(i = 0, j = 0; j < b.size() + dummies; j++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~
doll.cpp:67:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     if(i >= b.size() || rev(j, b.size()+dummies) < dummies) a.push_back(globalCurSwitch);
      |        ~~^~~~~~~~~~~
doll.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for(int i = 0; i < b.size(); i+=2) {
      |                  ~~^~~~~~~~~~
doll.cpp:91:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |   for(int i = 1; i < b.size(); i+=2) {
      |                  ~~^~~~~~~~~~
doll.cpp:97:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |   if(X.size() <= abs(curSwitch)-1) X.resize(abs(curSwitch)), Y.resize(abs(curSwitch));
      |      ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
doll.cpp:83:7: warning: variable 'nextDummies' set but not used [-Wunused-but-set-variable]
   83 |   int nextDummies = 0;
      |       ^~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:106:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |   for(int i = 1; i < A.size(); i++)
      |                  ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 60 ms 9336 KB Output is correct
3 Correct 56 ms 9460 KB Output is correct
4 Correct 6 ms 4940 KB Output is correct
5 Correct 17 ms 6072 KB Output is correct
6 Correct 81 ms 11636 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 60 ms 9336 KB Output is correct
3 Correct 56 ms 9460 KB Output is correct
4 Correct 6 ms 4940 KB Output is correct
5 Correct 17 ms 6072 KB Output is correct
6 Correct 81 ms 11636 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 95 ms 12476 KB Output is correct
9 Correct 136 ms 13040 KB Output is correct
10 Correct 186 ms 16792 KB Output is correct
11 Correct 5 ms 4940 KB Output is correct
12 Correct 6 ms 4940 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 60 ms 9336 KB Output is correct
3 Correct 56 ms 9460 KB Output is correct
4 Correct 6 ms 4940 KB Output is correct
5 Correct 17 ms 6072 KB Output is correct
6 Correct 81 ms 11636 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 95 ms 12476 KB Output is correct
9 Correct 136 ms 13040 KB Output is correct
10 Correct 186 ms 16792 KB Output is correct
11 Correct 5 ms 4940 KB Output is correct
12 Correct 6 ms 4940 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct
14 Correct 140 ms 16224 KB Output is correct
15 Correct 98 ms 12832 KB Output is correct
16 Correct 137 ms 16068 KB Output is correct
17 Correct 4 ms 4940 KB Output is correct
18 Correct 5 ms 4940 KB Output is correct
19 Correct 5 ms 4940 KB Output is correct
20 Correct 137 ms 16352 KB Output is correct
21 Correct 4 ms 4940 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Correct 5 ms 4940 KB Output is correct
8 Correct 5 ms 4940 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 81 ms 11048 KB Output is correct
3 Correct 95 ms 12620 KB Output is correct
4 Correct 141 ms 15012 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 81 ms 11048 KB Output is correct
3 Correct 95 ms 12620 KB Output is correct
4 Correct 141 ms 15012 KB Output is correct
5 Correct 135 ms 15928 KB Output is correct
6 Correct 161 ms 15796 KB Output is correct
7 Correct 150 ms 15836 KB Output is correct
8 Correct 139 ms 15372 KB Output is correct
9 Correct 111 ms 12652 KB Output is correct
10 Correct 130 ms 15588 KB Output is correct
11 Correct 129 ms 15048 KB Output is correct
12 Correct 95 ms 12608 KB Output is correct
13 Correct 85 ms 11512 KB Output is correct
14 Correct 101 ms 12740 KB Output is correct
15 Correct 107 ms 12792 KB Output is correct
16 Correct 8 ms 5196 KB Output is correct
17 Correct 81 ms 11784 KB Output is correct
18 Correct 82 ms 11252 KB Output is correct
19 Correct 98 ms 12732 KB Output is correct
20 Correct 129 ms 15508 KB Output is correct
21 Correct 159 ms 15316 KB Output is correct
22 Correct 136 ms 15336 KB Output is correct