oj.uz

Submission #75735

# Submission time Handle Problem Language Result Execution time Memory
75735 2018-09-10T20:51:46 Z KieranHorgan Mechanical Doll (IOI18_doll) C++17
100 / 100
 157 ms 11672 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> A, X, Y, C;

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

  int curSwitch = nextSwitch--;

  vector<int> a;
  for(int i = 0; i < b.size(); i+=2)
    a.push_back(b[i]);
  int l = a.back() == -1 ? -1 : recurseThroughTree(a);

  a.clear();
  for(int i = 1; i < b.size(); i+=2)
    a.push_back(b[i]);
  int r = a.back() == -1 ? -1 : 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 getDest(int x, int bits) {
  int res = 0;
  for(int i = 0; i < bits; i++)
    if(x & (1<<i))
      res |= 1<<(bits-1-i);
  return res;
}

void create_circuit(int M, vector<int> A_) {
  int N = A_.size();
  A = A_;
  A.push_back(0);
  C.assign(M+1, -1);

  int dummies = 0;
  while(__builtin_popcount(A.size()+dummies) != 1)
    dummies++;

  vector<int> b;
  int i, j;
  for(i = 0, j = 0; j < A.size() + dummies; j++) {
    if(i >= A.size() || getDest(j, __builtin_ctz(A.size()+dummies)) < dummies) b.push_back(-1);
    else b.push_back(A[i++]);
  }
  recurseThroughTree(b);

  answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'int recurseThroughTree(std::vector<int>)':
doll.cpp:14:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   for(int i = 0; i < b.size(); i+=2)
      |                  ~~^~~~~~~~~~
doll.cpp:19:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   for(int i = 1; i < b.size(); i+=2)
      |                  ~~^~~~~~~~~~
doll.cpp:23:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |   if(X.size() <= abs(curSwitch)-1) X.resize(abs(curSwitch)), Y.resize(abs(curSwitch));
      |      ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(i = 0, j = 0; j < A.size() + dummies; j++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~
doll.cpp:51:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     if(i >= A.size() || getDest(j, __builtin_ctz(A.size()+dummies)) < dummies) b.push_back(-1);
      |        ~~^~~~~~~~~~~
doll.cpp:39:7: warning: unused variable 'N' [-Wunused-variable]
   39 |   int N = A_.size();
      |       ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 53 ms 4908 KB Output is correct
3 Correct 55 ms 4508 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 12 ms 1392 KB Output is correct
6 Correct 73 ms 6456 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 53 ms 4908 KB Output is correct
3 Correct 55 ms 4508 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 12 ms 1392 KB Output is correct
6 Correct 73 ms 6456 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 95 ms 8224 KB Output is correct
9 Correct 98 ms 8344 KB Output is correct
10 Correct 135 ms 11672 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 53 ms 4908 KB Output is correct
3 Correct 55 ms 4508 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 12 ms 1392 KB Output is correct
6 Correct 73 ms 6456 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 95 ms 8224 KB Output is correct
9 Correct 98 ms 8344 KB Output is correct
10 Correct 135 ms 11672 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 132 ms 10688 KB Output is correct
15 Correct 104 ms 8004 KB Output is correct
16 Correct 137 ms 10572 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 148 ms 10828 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 88 ms 7996 KB Output is correct
3 Correct 90 ms 7952 KB Output is correct
4 Correct 136 ms 9476 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 88 ms 7996 KB Output is correct
3 Correct 90 ms 7952 KB Output is correct
4 Correct 136 ms 9476 KB Output is correct
5 Correct 127 ms 10424 KB Output is correct
6 Correct 127 ms 10372 KB Output is correct
7 Correct 157 ms 10312 KB Output is correct
8 Correct 133 ms 9988 KB Output is correct
9 Correct 85 ms 7992 KB Output is correct
10 Correct 130 ms 10096 KB Output is correct
11 Correct 121 ms 9760 KB Output is correct
12 Correct 86 ms 7940 KB Output is correct
13 Correct 90 ms 7968 KB Output is correct
14 Correct 101 ms 8000 KB Output is correct
15 Correct 91 ms 8000 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 80 ms 7840 KB Output is correct
18 Correct 101 ms 7932 KB Output is correct
19 Correct 87 ms 7944 KB Output is correct
20 Correct 147 ms 10004 KB Output is correct
21 Correct 128 ms 9740 KB Output is correct
22 Correct 118 ms 9852 KB Output is correct