oj.uz

Submission #75246

# Submission time Handle Problem Language Result Execution time Memory
75246 2018-09-09T01:48:52 Z KieranHorgan Mechanical Doll (IOI18_doll) C++17
37 / 100
 321 ms 68236 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
 
pair<int, int> exits[400005];
vector<int> X, Y, C;
bool stateIsX[400005];
int depth[400005];
int switchIdx = -1;
set<pair<int, int>> notSetToX;
void build(int cur, int par, int add) {
  if(cur > 0) {
    --switchIdx;
    if(X[-(par+1)] == cur) X[-(par+1)] = switchIdx;
    else Y[-(par+1)] = switchIdx;
    X.push_back(cur);
    Y.push_back(add);
    depth[-(switchIdx+1)] = depth[-(par+1)]+1;
    stateIsX[-(switchIdx+1)] = 1;
    return;
  }

  stateIsX[-(cur+1)] = !stateIsX[-(cur+1)];
  build(!stateIsX[-(cur+1)]?X[-(cur+1)]:Y[-(cur+1)], cur, add);
}

void resetAll(int cur, int par) {
  if(cur == 0) return;
  if(cur > 0) {
    --switchIdx;
    int add = notSetToX.begin()->second;
    // cerr << notSetToX.begin()->first << endl;
    notSetToX.erase(notSetToX.begin());
    if(X[-(par+1)] == cur) X[-(par+1)] = switchIdx;
    else Y[-(par+1)] = switchIdx;
    X.push_back(cur);
    Y.push_back(add);
    depth[-(switchIdx+1)] = depth[-(par+1)]+1;
    stateIsX[-(switchIdx+1)] = 1;
    resetAll(add, 0);
    return;
  }

  if(stateIsX[-(cur+1)]) notSetToX.insert({depth[-(cur+1)], cur});
  else notSetToX.erase({depth[-(cur+1)], cur});
  stateIsX[-(cur+1)] = !stateIsX[-(cur+1)];

  resetAll(!stateIsX[-(cur+1)]?X[-(cur+1)]:Y[-(cur+1)], cur);  
}
 
void create_circuit(int M, vector<int> A) {
  int N = A.size();

  if(N == 1) {
    answer({A[0], 0}, {}, {});
    return;
  }
  C.assign(M+1, -1);

  X.push_back(A[0]);
  Y.push_back(A[1]);
  stateIsX[0] = 1;

  for(int i = 2; i < A.size(); i++) {
    build(-1, 0, A[i]);
  }

  for(int i = -1; i >= switchIdx; i--) {
    notSetToX.insert({depth[-(i+1)], i});
  }
  notSetToX.insert({1<<30, 0});

  resetAll(-1, 0);

  // vector<int> C(M + 1);
  // C[0] = -1;
  // for (int i = 1; i <= M; ++i) {
    // C[i] = -1;
  // }
 
  // for(auto x: A[i]) {
    // build(-1, add);
  // }
 // 
  // for(int i = -1; i >= switchIdx; i--) {
    // X.push_back(exits[-(i+1)].first);
    // Y.push_back(exits[-(i+1)].second);
    // cerr << i << ": " << X[-(i+1)] << " " << Y[-(i+1)] << "  " << stateIsX[-(i+1)] << endl;
  // }


  // 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;

  // for(int i = 0; i < C.size(); i++)
    // cout << i << " " << C[i] << endl;
  // for(int i = 0; i < X.size(); i++) {
    // cout << -(i+1) << " " << X[i] << endl;
    // cout << -(i+1) << " " << Y[i] << endl;
  // }

  answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for(int i = 2; i < A.size(); i++) {
      |                  ~~^~~~~~~~~~

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 208 ms 48412 KB Output is partially correct
3 Partially correct 213 ms 50336 KB Output is partially correct
4 Partially correct 310 ms 67240 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 208 ms 48412 KB Output is partially correct
3 Partially correct 213 ms 50336 KB Output is partially correct
4 Partially correct 310 ms 67240 KB Output is partially correct
5 Partially correct 317 ms 68236 KB Output is partially correct
6 Partially correct 299 ms 68072 KB Output is partially correct
7 Partially correct 305 ms 68136 KB Output is partially correct
8 Partially correct 318 ms 67864 KB Output is partially correct
9 Partially correct 216 ms 50332 KB Output is partially correct
10 Partially correct 301 ms 67804 KB Output is partially correct
11 Partially correct 321 ms 67532 KB Output is partially correct
12 Partially correct 198 ms 50640 KB Output is partially correct
13 Partially correct 195 ms 49140 KB Output is partially correct
14 Partially correct 212 ms 51076 KB Output is partially correct
15 Partially correct 201 ms 51208 KB Output is partially correct
16 Partially correct 7 ms 1856 KB Output is partially correct
17 Partially correct 203 ms 48736 KB Output is partially correct
18 Partially correct 208 ms 48720 KB Output is partially correct
19 Partially correct 223 ms 50672 KB Output is partially correct
20 Partially correct 292 ms 67768 KB Output is partially correct
21 Partially correct 291 ms 67504 KB Output is partially correct
22 Partially correct 314 ms 67616 KB Output is partially correct