oj.uz

Submission #75305

# Submission time Handle Problem Language Result Execution time Memory
75305 2018-09-09T07:38:39 Z KieranHorgan Mechanical Doll (IOI18_doll) C++17
53 / 100
 221 ms 20688 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 recurseThroughTree(vector<int> b) {
  if(b.size() == 1) return b[0];
  int curSwitch = nextSwitch--;

  // cerr << curSwitch << ": ";
  // for(int i = 0; i < b.size(); i++)
    // cerr << b[i] << " ";
  // cerr << endl;

  vector<int> a;
  for(int i = 0; i < b.size(); i+=2)
    a.push_back(b[i]);
  int l = recurseThroughTree(a);
  a.clear();
  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;
  // cerr << curSwitch << ": " << l << " " << r << endl;
  return curSwitch;
}

void buildTree(int curTrigger, int curSwitch) {
  int last = AdjList[curTrigger].back();
  AdjList[curTrigger].pop_back();
  while(__builtin_popcount(AdjList[curTrigger].size()+1) != 1) AdjList[curTrigger].push_back(curSwitch);
  AdjList[curTrigger].push_back(last);

  // cerr << curTrigger << ": " << AdjList[curTrigger].size() << endl;
  // cerr << curSwitch << ": ";
  // for(int i = 0; i < AdjList[curTrigger].size(); i++)
    // cerr << AdjList[curTrigger][i] << " ";
  // cerr << endl;
  vector<int> a;
  for(int i = 0; i < AdjList[curTrigger].size(); i+=2)
    a.push_back(AdjList[curTrigger][i]);
  int l = recurseThroughTree(a);
  a.clear();
  for(int i = 1; i < AdjList[curTrigger].size(); i+=2)
    a.push_back(AdjList[curTrigger][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;
  // cerr << curSwitch << ": " << l << " " << r << endl;
}

void create_circuit(int M, vector<int> A_) {
  A = A_;
  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]);
    }
  }

  // cerr << nextSwitch << endl;
  // for(int i = 1; dep[i]; i++)
    // cerr << i << ": " << dep[i] << endl;
  // 
  // cerr << N << " " << X.size() << endl;


  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:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for(int i = 1; i < b.size(); i+=2)
      |                  ~~^~~~~~~~~~
doll.cpp:28:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |   if(X.size() <= abs(curSwitch)-1) X.resize(abs(curSwitch)), Y.resize(abs(curSwitch));
      |      ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
doll.cpp: In function 'void buildTree(int, int)':
doll.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i = 0; i < AdjList[curTrigger].size(); i+=2)
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
doll.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for(int i = 1; i < AdjList[curTrigger].size(); i+=2)
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
doll.cpp:55:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |   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:65:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i = 0; i+1 < 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 39 ms 8968 KB Output is correct
3 Correct 30 ms 8588 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 15 ms 6092 KB Output is correct
6 Correct 50 ms 10380 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 4 ms 4940 KB Output is correct
2 Correct 39 ms 8968 KB Output is correct
3 Correct 30 ms 8588 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 15 ms 6092 KB Output is correct
6 Correct 50 ms 10380 KB Output is correct
7 Correct 5 ms 4940 KB Output is correct
8 Correct 66 ms 10996 KB Output is correct
9 Correct 74 ms 11500 KB Output is correct
10 Correct 121 ms 14188 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 5 ms 4940 KB Output is correct
13 Correct 5 ms 4980 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 39 ms 8968 KB Output is correct
3 Correct 30 ms 8588 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 15 ms 6092 KB Output is correct
6 Correct 50 ms 10380 KB Output is correct
7 Correct 5 ms 4940 KB Output is correct
8 Correct 66 ms 10996 KB Output is correct
9 Correct 74 ms 11500 KB Output is correct
10 Correct 121 ms 14188 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 5 ms 4940 KB Output is correct
13 Correct 5 ms 4980 KB Output is correct
14 Correct 124 ms 15700 KB Output is correct
15 Correct 66 ms 11056 KB Output is correct
16 Correct 103 ms 13284 KB Output is correct
17 Correct 4 ms 4940 KB Output is correct
18 Correct 4 ms 4940 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Correct 109 ms 14772 KB Output is correct
21 Correct 6 ms 4940 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 4944 KB Output is partially correct
2 Correct 80 ms 10868 KB Output is correct
3 Partially correct 125 ms 15984 KB Output is partially correct
4 Partially correct 137 ms 16464 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 4944 KB Output is partially correct
2 Correct 80 ms 10868 KB Output is correct
3 Partially correct 125 ms 15984 KB Output is partially correct
4 Partially correct 137 ms 16464 KB Output is partially correct
5 Partially correct 158 ms 17748 KB Output is partially correct
6 Partially correct 170 ms 18908 KB Output is partially correct
7 Partially correct 163 ms 18480 KB Output is partially correct
8 Partially correct 221 ms 19552 KB Output is partially correct
9 Partially correct 122 ms 15288 KB Output is partially correct
10 Partially correct 186 ms 20688 KB Output is partially correct
11 Partially correct 184 ms 20328 KB Output is partially correct
12 Partially correct 137 ms 15184 KB Output is partially correct
13 Partially correct 112 ms 14136 KB Output is partially correct
14 Partially correct 109 ms 13752 KB Output is partially correct
15 Partially correct 105 ms 13356 KB Output is partially correct
16 Partially correct 8 ms 5256 KB Output is partially correct
17 Partially correct 117 ms 12736 KB Output is partially correct
18 Partially correct 101 ms 12636 KB Output is partially correct
19 Partially correct 106 ms 13564 KB Output is partially correct
20 Partially correct 155 ms 15716 KB Output is partially correct
21 Partially correct 171 ms 17984 KB Output is partially correct
22 Partially correct 135 ms 14940 KB Output is partially correct