oj.uz

Submission #75260

# Submission time Handle Problem Language Result Execution time Memory
75260 2018-09-09T03:44:20 Z KieranHorgan Mechanical Doll (IOI18_doll) C++17
37 / 100
 337 ms 68240 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);

  // cout << M << endl;
  // for(auto x: A)
    // cout << x << endl;
}

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 2 ms 276 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 276 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 276 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 199 ms 48464 KB Output is partially correct
3 Partially correct 198 ms 50308 KB Output is partially correct
4 Partially correct 290 ms 67180 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 199 ms 48464 KB Output is partially correct
3 Partially correct 198 ms 50308 KB Output is partially correct
4 Partially correct 290 ms 67180 KB Output is partially correct
5 Partially correct 295 ms 68240 KB Output is partially correct
6 Partially correct 322 ms 68096 KB Output is partially correct
7 Partially correct 311 ms 68088 KB Output is partially correct
8 Partially correct 307 ms 67888 KB Output is partially correct
9 Partially correct 190 ms 50404 KB Output is partially correct
10 Partially correct 298 ms 67772 KB Output is partially correct
11 Partially correct 301 ms 67556 KB Output is partially correct
12 Partially correct 207 ms 50656 KB Output is partially correct
13 Partially correct 192 ms 49052 KB Output is partially correct
14 Partially correct 194 ms 51100 KB Output is partially correct
15 Partially correct 209 ms 51212 KB Output is partially correct
16 Partially correct 6 ms 1856 KB Output is partially correct
17 Partially correct 200 ms 48768 KB Output is partially correct
18 Partially correct 210 ms 48668 KB Output is partially correct
19 Partially correct 208 ms 50632 KB Output is partially correct
20 Partially correct 337 ms 67740 KB Output is partially correct
21 Partially correct 330 ms 67580 KB Output is partially correct
22 Partially correct 302 ms 67580 KB Output is partially correct