oj.uz

Submission #75249

# Submission time Handle Problem Language Result Execution time Memory
75249 2018-09-09T02:36:29 Z KieranHorgan Mechanical Doll (IOI18_doll) C++17
37 / 100
 330 ms 68260 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 192 ms 48488 KB Output is partially correct
3 Partially correct 196 ms 50332 KB Output is partially correct
4 Partially correct 295 ms 67144 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 192 ms 48488 KB Output is partially correct
3 Partially correct 196 ms 50332 KB Output is partially correct
4 Partially correct 295 ms 67144 KB Output is partially correct
5 Partially correct 311 ms 68260 KB Output is partially correct
6 Partially correct 296 ms 68024 KB Output is partially correct
7 Partially correct 291 ms 68148 KB Output is partially correct
8 Partially correct 296 ms 67832 KB Output is partially correct
9 Partially correct 211 ms 50380 KB Output is partially correct
10 Partially correct 309 ms 67816 KB Output is partially correct
11 Partially correct 312 ms 67528 KB Output is partially correct
12 Partially correct 194 ms 50668 KB Output is partially correct
13 Partially correct 208 ms 49180 KB Output is partially correct
14 Partially correct 209 ms 51112 KB Output is partially correct
15 Partially correct 211 ms 51220 KB Output is partially correct
16 Partially correct 6 ms 1856 KB Output is partially correct
17 Partially correct 209 ms 48676 KB Output is partially correct
18 Partially correct 204 ms 48660 KB Output is partially correct
19 Partially correct 192 ms 50636 KB Output is partially correct
20 Partially correct 312 ms 67804 KB Output is partially correct
21 Partially correct 299 ms 67544 KB Output is partially correct
22 Partially correct 330 ms 67504 KB Output is partially correct