oj.uz

Submission #218311

# Submission time Handle Problem Language Result Execution time Memory
218311 2020-04-02T00:26:40 Z edsa Mechanical Doll (IOI18_doll) C++14
26 / 100
 112 ms 19680 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
const ll MOD = 998244353;
const int INF = 1e9+9;
const int MAXN = 200005;

#include "doll.h"

int sm[2*MAXN], add[2*MAXN], nxt[MAXN];
vi gr[MAXN];
vi C, X, Y;

void create_circuit(int M, vector<int> A) {
    for (int i = 1; i < (int) A.size(); ++i) {
        gr[A[i-1]].push_back(A[i]);
    }
    gr[A.back()].push_back(0);
    C.resize(M+1);
    C[0] = A[0];

    for (int i = 1; i <= M; ++i) {
        if (gr[i].empty()) {
            C[i] = 0;
            continue;
        }
        if (gr[i].size() == 1) {
            C[i] = gr[i][0];
            continue;
        }

        int n = 2;
        while (n < (int)gr[i].size())
            n<<=1;
        int extra = n-(int)gr[i].size();
        int fSw = X.size(); // first new switch
        C[i] = -fSw-1;

        sm[1] = 0;
        add[1] = 1;
        for (int j = 1; j < n; ++j) {
            sm[j<<1] = sm[j];
            sm[j<<1|1] = sm[j]+add[j];
            add[j<<1] = add[j<<1|1] = add[j]<<1;
        }
        for (int j = 0, erased = 0; j < n; ++j) {
            if (sm[n+j] < extra) {
                erased++;
            } else {
                nxt[sm[n+j]] = gr[i][j-erased];
            }
        }

        sm[fSw] = 0;
        add[fSw] = n>>1;
        X.emplace_back(), Y.emplace_back();
        for (int s = fSw; s < (int) X.size(); ++s) {
            if (add[s] == 1) {
                X[s] = sm[s] < extra? -fSw-1 : nxt[sm[s]];
                Y[s] = nxt[sm[s]+1];
                continue;
            }
            if (sm[s]+add[s] <= extra) {
                X[s] = -fSw-1;
            } else {
                X[s] = -X.size()-1;
                sm[X.size()] = sm[s];
                add[X.size()] = add[s]>>1;
                X.emplace_back(), Y.emplace_back();
            }
            Y[s] = -X.size()-1;
            sm[X.size()] = sm[s]+add[s];
            add[X.size()] = add[s]>>1;
            X.emplace_back(), Y.emplace_back();
        }
    }

    // for (int i = 0; i <= M; ++i) {
    //     cerr << C[i] << ' ';
    // }
    // cerr << endl;
    // for (int i = 0; i < (int) X.size(); ++i) {
    //     cerr << X[i] << ' ' << Y[i] << endl;
    // }
    answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 35 ms 8716 KB Output is correct
3 Correct 33 ms 8340 KB Output is correct
4 Correct 5 ms 4940 KB Output is correct
5 Correct 19 ms 6092 KB Output is correct
6 Correct 51 ms 10052 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 35 ms 8716 KB Output is correct
3 Correct 33 ms 8340 KB Output is correct
4 Correct 5 ms 4940 KB Output is correct
5 Correct 19 ms 6092 KB Output is correct
6 Correct 51 ms 10052 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 63 ms 11008 KB Output is correct
9 Correct 63 ms 11364 KB Output is correct
10 Correct 103 ms 14160 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 5 ms 4940 KB Output is correct
13 Correct 5 ms 4940 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 35 ms 8716 KB Output is correct
3 Correct 33 ms 8340 KB Output is correct
4 Correct 5 ms 4940 KB Output is correct
5 Correct 19 ms 6092 KB Output is correct
6 Correct 51 ms 10052 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 63 ms 11008 KB Output is correct
9 Correct 63 ms 11364 KB Output is correct
10 Correct 103 ms 14160 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 5 ms 4940 KB Output is correct
13 Correct 5 ms 4940 KB Output is correct
14 Correct 112 ms 16476 KB Output is correct
15 Correct 58 ms 10624 KB Output is correct
16 Correct 91 ms 13664 KB Output is correct
17 Correct 4 ms 4940 KB Output is correct
18 Correct 5 ms 4940 KB Output is correct
19 Correct 4 ms 4940 KB Output is correct
20 Correct 107 ms 15180 KB Output is correct
21 Correct 5 ms 4940 KB Output is correct
22 Correct 3 ms 4940 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 51 ms 12552 KB Output is correct
3 Runtime error 36 ms 19680 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 51 ms 12552 KB Output is correct
3 Runtime error 36 ms 19680 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -