oj.uz

Submission #1075127

# Submission time Handle Problem Language Result Execution time Memory
1075127 2024-08-25T18:49:09 Z TB_ Mechanical Doll (IOI18_doll) C++17
53 / 100
 81 ms 18064 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fo(i, n) for(ll i = 0; i<(n); i++)
#define pb push_back
#define F first
#define S second
#define deb(x) cout << #x << " = " << (x) << endl 
#define deb2(x, y) cout << #x << " = " << (x)  << ", " << #y << " = " << (y) << endl 
typedef vector<ll> vl;
typedef vector<vl> vvl;

// void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y){

// }
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
void create_circuit(int M, std::vector<int> A){
    vvl adj(M+1);
    ll n = A.size();
    adj[0].pb(A[0]);
    fo(i, n){
        if(i<n-1) adj[A[i]].pb(A[i+1]);
        else adj[A[i]].pb(0);
    }
    ll cou = 0;
    vector<int> c, x, y;
    fo(i, M+1){
        cou = x.size();
        ll co = 0;
        if(adj[i].size() == 0){
            c.pb(i);
            continue;
        }
        else if(adj[i].size() == 1){
            c.pb(adj[i][0]);
            continue;
        }
        c.pb(-cou-1);
        ll am = adj[i].size();
        ll ext = 1;
        while(ext<am) ext*=2ll;
        ll am2 = ext-am;
        vl order(ext*2);
        vl state(ext, 0);
        // deb(ext);
        fo(j, ext){
            ll current = 1;
            while(current<ext){
                ll sta = state[current]; 
                state[current] = !state[current];
                current*=2;
                if(sta)current++;
            }
            // deb(am2);
            // deb2(ext-current-1, am2);
            if(current<am2+ext) order[current] = (-cou-1);
            else order[current] = (adj[i][co++]);
            // deb2(current, order[current]);
        }
        co= 0;
        fo(i, ext){
            if(!i) continue;
            if(i*2<ext){
                if(order[(-cou-i*2)*2] == order[(-cou-i*2)*2+1] && 0) x.pb(order[(-cou-i*2)*2]);
                else x.pb(-cou-i*2);
                if(order[(-cou-i*2-1)*2] == order[(-cou-i*2-1)*2+1] && 0) y.pb(order[(-cou-i*2-1)*2]);
                else y.pb(-cou-i*2-1);
            }else{
                x.pb(order[i*2]);
                y.pb(order[i*2+1]);

            }

        }
    }
    // fo(i, c.size()){
    //     deb(c[i]);
    // }
    // fo(i, x.size()){
    //     deb2(x[i], y[i]);
    // }
    answer(c, x, y);
}



// int main(){

//     // vector<int> st = {1, 2, 1, 3};
//     vector<int> st = {1, 2, 1, 2, 1};
//     create_circuit(3, st);

//     return 0;
// }

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 17 ms 6920 KB Output is correct
3 Correct 17 ms 5700 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 8 ms 4052 KB Output is correct
6 Correct 25 ms 8676 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 17 ms 6920 KB Output is correct
3 Correct 17 ms 5700 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 8 ms 4052 KB Output is correct
6 Correct 25 ms 8676 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 33 ms 8076 KB Output is correct
9 Correct 35 ms 9684 KB Output is correct
10 Correct 61 ms 12608 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 17 ms 6920 KB Output is correct
3 Correct 17 ms 5700 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 8 ms 4052 KB Output is correct
6 Correct 25 ms 8676 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 33 ms 8076 KB Output is correct
9 Correct 35 ms 9684 KB Output is correct
10 Correct 61 ms 12608 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 59 ms 14352 KB Output is correct
15 Correct 31 ms 7688 KB Output is correct
16 Correct 53 ms 11488 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 60 ms 13316 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Correct 45 ms 7624 KB Output is correct
3 Partially correct 62 ms 12996 KB Output is partially correct
4 Partially correct 63 ms 14536 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Correct 45 ms 7624 KB Output is correct
3 Partially correct 62 ms 12996 KB Output is partially correct
4 Partially correct 63 ms 14536 KB Output is partially correct
5 Partially correct 65 ms 15028 KB Output is partially correct
6 Partially correct 70 ms 15544 KB Output is partially correct
7 Partially correct 66 ms 15492 KB Output is partially correct
8 Partially correct 67 ms 15800 KB Output is partially correct
9 Partially correct 54 ms 11324 KB Output is partially correct
10 Partially correct 81 ms 18064 KB Output is partially correct
11 Partially correct 65 ms 16308 KB Output is partially correct
12 Partially correct 43 ms 10864 KB Output is partially correct
13 Partially correct 42 ms 10172 KB Output is partially correct
14 Partially correct 42 ms 10176 KB Output is partially correct
15 Partially correct 43 ms 9920 KB Output is partially correct
16 Partially correct 2 ms 600 KB Output is partially correct
17 Partially correct 36 ms 9072 KB Output is partially correct
18 Partially correct 35 ms 9056 KB Output is partially correct
19 Partially correct 38 ms 9672 KB Output is partially correct
20 Partially correct 58 ms 12468 KB Output is partially correct
21 Partially correct 64 ms 14428 KB Output is partially correct
22 Partially correct 50 ms 11620 KB Output is partially correct