oj.uz

Submission #75270

# Submission time Handle Problem Language Result Execution time Memory
75270 2018-09-09T05:07:51 Z KieranHorgan Mechanical Doll (IOI18_doll) C++17
37 / 100
 173 ms 13316 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
 
pair<int, int> exits[400005];
vector<int> X, Y;
int nodeIdx = 1;
vector<int> dep[300];
int build(vector<int> cur) {
  if(cur.size() == 1) {
    return cur[0];
  }

  int curNode = nodeIdx++;

  vector<int> nextCur;
  for(int i = 0; i < cur.size(); i+=2) {
    nextCur.push_back(cur[i]);
  }
  exits[curNode].first = build(nextCur);
  nextCur.clear();
 
  for(int i = 1; i < cur.size(); i+=2) {
    nextCur.push_back(cur[i]);
  }
  exits[curNode].second = build(nextCur);
  nextCur.clear();
  return -curNode;
}
 
void create_circuit(int M, vector<int> A) {
  int N = A.size();
  while(__builtin_popcount(A.size()+1) != 1) {
    A.push_back(-1);
  }
  A.push_back(0);
  cerr << A.size() << endl;

  vector<int> C(M + 1);
  C[0] = -1;
  for (int i = 1; i <= M; ++i) {
    C[i] = -1;
  }
 
  vector<int> cur;
  for(int i = 0; i < A.size(); i++) {
    cur.push_back(A[i]);
  }
  cur.back() = -cur.back();
 
  build(cur);

  for(int i = 1; i < nodeIdx; i++) {
    X.push_back(exits[i].first);
    Y.push_back(exits[i].second);
  }

  answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'int build(std::vector<int>)':
doll.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   for(int i = 0; i < cur.size(); i+=2) {
      |                  ~~^~~~~~~~~~~~
doll.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   for(int i = 1; i < cur.size(); i+=2) {
      |                  ~~^~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for(int i = 0; i < A.size(); i++) {
      |                  ~~^~~~~~~~~~
doll.cpp:32:7: warning: unused variable 'N' [-Wunused-variable]
   32 |   int N = A.size();
      |       ^

Subtask #1
0 / 2.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Partially correct 154 ms 12592 KB Output is partially correct
3 Partially correct 121 ms 12592 KB Output is partially correct
4 Partially correct 157 ms 12340 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Partially correct 154 ms 12592 KB Output is partially correct
3 Partially correct 121 ms 12592 KB Output is partially correct
4 Partially correct 157 ms 12340 KB Output is partially correct
5 Partially correct 137 ms 12844 KB Output is partially correct
6 Partially correct 151 ms 12748 KB Output is partially correct
7 Partially correct 138 ms 12740 KB Output is partially correct
8 Partially correct 133 ms 12640 KB Output is partially correct
9 Partially correct 123 ms 12660 KB Output is partially correct
10 Partially correct 173 ms 12652 KB Output is partially correct
11 Partially correct 147 ms 12368 KB Output is partially correct
12 Partially correct 126 ms 12844 KB Output is partially correct
13 Partially correct 124 ms 13216 KB Output is partially correct
14 Partially correct 138 ms 13188 KB Output is partially correct
15 Partially correct 132 ms 13316 KB Output is partially correct
16 Partially correct 5 ms 768 KB Output is partially correct
17 Correct 92 ms 7900 KB Output is correct
18 Partially correct 120 ms 12828 KB Output is partially correct
19 Partially correct 123 ms 12848 KB Output is partially correct
20 Partially correct 130 ms 12336 KB Output is partially correct
21 Partially correct 133 ms 12340 KB Output is partially correct
22 Partially correct 126 ms 12348 KB Output is partially correct