oj.uz

Submission #560710

# Submission time Handle Problem Language Result Execution time Memory
560710 2022-05-12T00:53:18 Z tfg Mechanical Doll (IOI18_doll) C++17
84 / 100
 135 ms 7676 KB 
#include "doll.h"

const int MAGIC = 1e9;

std::vector<int> X, Y;

int solve(int sz) {
    int id = (int) X.size();
    X.push_back(MAGIC), Y.push_back(MAGIC);
    if(sz == 1) {
        X[id] = -id-1;
    } else if(sz > 2) {
        X[id] = solve(sz/2);
        Y[id] = solve(sz/2);
    }
    return -id-1;
}

int outerSolve(const std::vector<int> &A) {
    int n = (int) A.size();
    if(n == 1) {
        solve(1);
        Y.back() = A.back();
    }
    int id = 0;
    while((1 << id) * 2 <= n) id++;
    for(int i = 0; i <= id; i++) {
        X.push_back(((1 << (id - i)) & n) ? MAGIC : -1), Y.push_back(-(i+1)-1);
    }
    Y.back() = A.back();
    for(int i = 0; i < id; i++) {
        if(X[i] == MAGIC) {
            X[i] = solve(1 << (id - i));
            //std::cout << "tree for 2^" << (id-i) << " in " << X[i] << std::endl;
        }
    }
    std::vector<bool> state(X.size(), false);
    bool wasted = false;
    for(int i = 0; i < (int) X.size(); i++) {
        //std::cout << -(i+1) << ": " << X[i] << ", " << Y[i] << '\n';
    }
    for(auto val : A) {
        int on = -1;
        //std::cout << "val is " << val << std::endl;
        while(on < 0) {
            //std::cout << "on " << on << std::endl;
            //assert(on < 0);
            state[-on-1] = !state[-on-1];
            int &nxt = (state[-on-1] ? X : Y)[-on-1];
            if(nxt == MAGIC && !wasted) {
                nxt = -1;
                wasted = true;
            } else if(nxt >= 0) {
                //assert(nxt == MAGIC || nxt == val);
                nxt = val;
            }
            on = nxt;
        }
        //assert(on == val);
    }
    for(int i = 0; i < (int) X.size(); i++) {
        //assert(!state[i]);
    }
    return -1;
}

void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  std::vector<int> C(M + 1, -1);
  C[0] = A[0];
  A.erase(A.begin());
  A.push_back(0);
  outerSolve(A);
  answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:68:7: warning: unused variable 'N' [-Wunused-variable]
   68 |   int N = A.size();
      |       ^

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 48 ms 4056 KB Output is correct
3 Correct 47 ms 3960 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 11 ms 1364 KB Output is correct
6 Correct 69 ms 5400 KB Output is correct
7 Incorrect 0 ms 212 KB wrong serial number
8 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 48 ms 4056 KB Output is correct
3 Correct 47 ms 3960 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 11 ms 1364 KB Output is correct
6 Correct 69 ms 5400 KB Output is correct
7 Incorrect 0 ms 212 KB wrong serial number
8 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 48 ms 4056 KB Output is correct
3 Correct 47 ms 3960 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 11 ms 1364 KB Output is correct
6 Correct 69 ms 5400 KB Output is correct
7 Incorrect 0 ms 212 KB wrong serial number
8 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 272 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 99 ms 5380 KB Output is correct
3 Correct 81 ms 5336 KB Output is correct
4 Correct 120 ms 7084 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 99 ms 5380 KB Output is correct
3 Correct 81 ms 5336 KB Output is correct
4 Correct 120 ms 7084 KB Output is correct
5 Correct 131 ms 7676 KB Output is correct
6 Correct 124 ms 7548 KB Output is correct
7 Correct 129 ms 7604 KB Output is correct
8 Correct 126 ms 7344 KB Output is correct
9 Correct 81 ms 5340 KB Output is correct
10 Correct 122 ms 7200 KB Output is correct
11 Correct 125 ms 7040 KB Output is correct
12 Correct 85 ms 5672 KB Output is correct
13 Correct 87 ms 5940 KB Output is correct
14 Correct 90 ms 6048 KB Output is correct
15 Correct 90 ms 6280 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 76 ms 4860 KB Output is correct
18 Correct 78 ms 5592 KB Output is correct
19 Correct 82 ms 5636 KB Output is correct
20 Correct 131 ms 7104 KB Output is correct
21 Correct 133 ms 7068 KB Output is correct
22 Correct 135 ms 7008 KB Output is correct