oj.uz

Submission #413527

# Submission time Handle Problem Language Result Execution time Memory
413527 2021-05-28T20:05:40 Z xyz Mechanical Doll (IOI18_doll) C++17
100 / 100
 253 ms 12180 KB 
#include <bits/stdc++.h>
#include "doll.h"
using namespace std;

const int N = 3e5;
int to[N];
bool done[N][2];

vector<pair<int, int>> sw; // switches

int build(int l, int r, int k){
    if(l > r)
        return 1;
    int v = sw.size();
    sw.push_back({-1, -1});
    if(k <= 0){
        done[v][1] = true;
        if(r - l == 1)
            done[v][0] = true;
    }
    if(r - l + 1 <= 2 && k <= 0)
        return v;
    assert(k >= 0);
    sw[v].second = -build(max(l, r - (1 << k) + 1), r, k - 1);
    sw[v].first = -build(l, r - (1 << k), k - 1);
    return v;
}

void create_circuit(int M, vector<int> A) {
    int n = A.size();

    const int Q = 99999999;
    sw.push_back({Q, Q}); // just to make 1-idx
    vector<int> out(M + 1);
    A.push_back(0);
    for(int i = n - 1; i >= 0; i --)
        swap(A[i], A[i + 1]);
    ++ n;
    A.push_back(0);

    int k = 0;
    while((1 << (k + 1)) < n)
        ++ k;
    int start = build(0, n - 1, k);
    for(int i = 1; i < sw.size(); i ++){
        done[i][0] ^= 1;
        done[i][1] ^= 1;
    }
    for(int j = 0; j < n; j ++){
        int v = start;
        bool found = false;
        while(!found){
            int was = v;
            if(to[v] == 1){
                if(sw[v].second == -start && !done[v][1]){
                    found = true;
                    done[v][1] = true;
                    sw[v].second = A[j + 1];
                }else{
                    v = -sw[v].second;
                }
            }else{
                if(sw[v].first == -start && !done[v][0]){
                    found = true;
                    done[v][0] = true;
                    sw[v].first = A[j + 1];
                }else{
                    v = -sw[v].first;
                }
            }
            to[was] ^= 1;
        }
    }

    for(int i = 0; i <= M; i ++)
        out[i] = -start;
    int S = sw.size();
    vector<int> X(S - 1), Y(S - 1);
    for(int i = 1; i < S; i ++)
        X[i - 1] = sw[i].first, Y[i - 1] = sw[i].second;
    answer(out, X, Y);
}

Compilation message

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 54 ms 4876 KB Output is correct
3 Correct 58 ms 4536 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 70 ms 6684 KB Output is correct
7 Correct 1 ms 256 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 54 ms 4876 KB Output is correct
3 Correct 58 ms 4536 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 70 ms 6684 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 92 ms 7996 KB Output is correct
9 Correct 253 ms 8484 KB Output is correct
10 Correct 137 ms 12180 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 2 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 54 ms 4876 KB Output is correct
3 Correct 58 ms 4536 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 70 ms 6684 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 92 ms 7996 KB Output is correct
9 Correct 253 ms 8484 KB Output is correct
10 Correct 137 ms 12180 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 2 ms 204 KB Output is correct
14 Correct 155 ms 11900 KB Output is correct
15 Correct 81 ms 7628 KB Output is correct
16 Correct 144 ms 11820 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 138 ms 12024 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 84 ms 6840 KB Output is correct
3 Correct 73 ms 6824 KB Output is correct
4 Correct 117 ms 10396 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 84 ms 6840 KB Output is correct
3 Correct 73 ms 6824 KB Output is correct
4 Correct 117 ms 10396 KB Output is correct
5 Correct 123 ms 11512 KB Output is correct
6 Correct 123 ms 11420 KB Output is correct
7 Correct 122 ms 11552 KB Output is correct
8 Correct 121 ms 11104 KB Output is correct
9 Correct 76 ms 6820 KB Output is correct
10 Correct 121 ms 11160 KB Output is correct
11 Correct 129 ms 10788 KB Output is correct
12 Correct 87 ms 7080 KB Output is correct
13 Correct 81 ms 7480 KB Output is correct
14 Correct 80 ms 7604 KB Output is correct
15 Correct 81 ms 7740 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 76 ms 7124 KB Output is correct
18 Correct 96 ms 7100 KB Output is correct
19 Correct 75 ms 7092 KB Output is correct
20 Correct 124 ms 10888 KB Output is correct
21 Correct 119 ms 10740 KB Output is correct
22 Correct 119 ms 10780 KB Output is correct