oj.uz

Submission #75282

# Submission time Handle Problem Language Result Execution time Memory
75282 2018-09-09T05:44:07 Z KieranHorgan Mechanical Doll (IOI18_doll) C++17
37 / 100
 170 ms 13296 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);
  }

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

  if(X.size() > N*2)
    exit(-1);

  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:65:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |   if(X.size() > N*2)
      |      ~~~~~~~~~^~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 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 2 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 2 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 2 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 128 ms 12692 KB Output is partially correct
3 Partially correct 145 ms 12596 KB Output is partially correct
4 Partially correct 149 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 128 ms 12692 KB Output is partially correct
3 Partially correct 145 ms 12596 KB Output is partially correct
4 Partially correct 149 ms 12340 KB Output is partially correct
5 Partially correct 143 ms 12844 KB Output is partially correct
6 Partially correct 138 ms 12636 KB Output is partially correct
7 Partially correct 139 ms 12708 KB Output is partially correct
8 Partially correct 142 ms 12492 KB Output is partially correct
9 Partially correct 153 ms 12624 KB Output is partially correct
10 Partially correct 162 ms 12444 KB Output is partially correct
11 Partially correct 128 ms 12312 KB Output is partially correct
12 Partially correct 132 ms 12836 KB Output is partially correct
13 Partially correct 130 ms 13136 KB Output is partially correct
14 Partially correct 126 ms 13228 KB Output is partially correct
15 Partially correct 124 ms 13296 KB Output is partially correct
16 Partially correct 5 ms 716 KB Output is partially correct
17 Correct 70 ms 7840 KB Output is correct
18 Partially correct 128 ms 12840 KB Output is partially correct
19 Partially correct 136 ms 12908 KB Output is partially correct
20 Partially correct 165 ms 12424 KB Output is partially correct
21 Partially correct 149 ms 12316 KB Output is partially correct
22 Partially correct 170 ms 12332 KB Output is partially correct