oj.uz

Submission #75717

# Submission time Handle Problem Language Result Execution time Memory
75717 2018-09-10T19:06:21 Z KieranHorgan Mechanical Doll (IOI18_doll) C++17
85.553 / 100
 172 ms 16496 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();

  if(!A.empty()) {
    AdjList[0].push_back(A[0]);
    for(int i = 0; i+1 < A.size(); i++) {
      AdjList[A[i]].push_back(A[i+1]);
    }
    AdjList[A.back()].push_back(0);
  }

  C.assign(M+1, 0);
  for(int i = 0; i <= M; i++) {
    if(AdjList[i].empty()) {
    } else if(AdjList[i].size() == 1) {
      C[i] = AdjList[i][0];
    } else {
      C[i] = nextSwitch--;
      buildTree(i, C[i]);
      // for(int j = C[i]; j > nextSwitch; j--) {
        // cerr << j << ": " << X[abs(j)-1] << " " << Y[abs(j)-1] << endl;
      // }
    }
  }

  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:108:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for(int i = 0; i+1 < A.size(); i++) {
      |                    ~~~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 38 ms 9000 KB Output is correct
3 Correct 27 ms 8524 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 16 ms 6092 KB Output is correct
6 Correct 48 ms 10444 KB Output is correct
7 Correct 5 ms 4940 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 38 ms 9000 KB Output is correct
3 Correct 27 ms 8524 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 16 ms 6092 KB Output is correct
6 Correct 48 ms 10444 KB Output is correct
7 Correct 5 ms 4940 KB Output is correct
8 Correct 66 ms 11032 KB Output is correct
9 Correct 82 ms 11528 KB Output is correct
10 Correct 127 ms 14212 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 4 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 5 ms 4940 KB Output is correct
2 Correct 38 ms 9000 KB Output is correct
3 Correct 27 ms 8524 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 16 ms 6092 KB Output is correct
6 Correct 48 ms 10444 KB Output is correct
7 Correct 5 ms 4940 KB Output is correct
8 Correct 66 ms 11032 KB Output is correct
9 Correct 82 ms 11528 KB Output is correct
10 Correct 127 ms 14212 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 4 ms 4940 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct
14 Correct 133 ms 15616 KB Output is correct
15 Correct 71 ms 11108 KB Output is correct
16 Correct 128 ms 13260 KB Output is correct
17 Correct 4 ms 4940 KB Output is correct
18 Correct 4 ms 5056 KB Output is correct
19 Correct 5 ms 4940 KB Output is correct
20 Correct 126 ms 14740 KB Output is correct
21 Correct 5 ms 4940 KB Output is correct
22 Correct 5 ms 4940 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 5 ms 4940 KB Output is correct
5 Correct 5 ms 4940 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 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 97 ms 11020 KB Output is correct
3 Correct 112 ms 12656 KB Output is correct
4 Correct 158 ms 15012 KB Output is correct

Subtask #6
41.5530038336 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 97 ms 11020 KB Output is correct
3 Correct 112 ms 12656 KB Output is correct
4 Correct 158 ms 15012 KB Output is correct
5 Partially correct 150 ms 16496 KB Output is partially correct
6 Partially correct 144 ms 16140 KB Output is partially correct
7 Partially correct 142 ms 16192 KB Output is partially correct
8 Partially correct 137 ms 15396 KB Output is partially correct
9 Partially correct 89 ms 10988 KB Output is partially correct
10 Partially correct 147 ms 14256 KB Output is partially correct
11 Partially correct 131 ms 14032 KB Output is partially correct
12 Partially correct 87 ms 11236 KB Output is partially correct
13 Partially correct 117 ms 12248 KB Output is partially correct
14 Partially correct 110 ms 12308 KB Output is partially correct
15 Partially correct 109 ms 12512 KB Output is partially correct
16 Partially correct 7 ms 5196 KB Output is partially correct
17 Partially correct 82 ms 10700 KB Output is partially correct
18 Partially correct 92 ms 10748 KB Output is partially correct
19 Partially correct 79 ms 10736 KB Output is partially correct
20 Partially correct 172 ms 13708 KB Output is partially correct
21 Partially correct 121 ms 13656 KB Output is partially correct
22 Partially correct 125 ms 13344 KB Output is partially correct