oj.uz

Submission #983658

# Submission time Handle Problem Language Result Execution time Memory
983658 2024-05-15T21:38:42 Z mariaclara Mechanical Doll (IOI18_doll) C++17
10 / 100
 1000 ms 10792 KB 
#include "doll.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 4e5+5; 
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int N;
vector<int> ans, S_x, S_y, state;
int create(int qnt) {
    if(qnt == 1) return 1;
    int a = create(qnt/2), b = create(qnt/2);
    S_x.pb(a);
    S_y.pb(b);
    //cout << "creating: " << qnt << "\nreturn: " << -sz(S_y) << "\n";
    return -sz(S_y);
}

void dfs(int x, int qtd) {
    if(qtd == N) return;
    //cout << x << " " << qtd << " " << state[-x-1] << "\n";
    if(state[-x-1] == 0) {
        state[-x-1] = 1;
        if(S_x[-x-1] == 1) S_x[-x-1] = qtd, dfs(-sz(S_x), qtd+1);
        else dfs(S_x[-x-1], qtd); 
    } 
    else {
        state[-x-1] = 0;
        if(S_y[-x-1] == 1) S_y[-x-1] = qtd, dfs(-sz(S_x), qtd+1);
        else dfs(S_y[-x-1], qtd); 
    }
}
void create_circuit(int M, vector<int> A) {
    A.pb(0);
    N = sz(A);
    
    vector<int> pot;
    for(int i = 20; i >= 0; i--)
        if(N >= (1<<i)) pot.pb(i), N -= (1<<i);

    N = sz(A);

    reverse(all(pot));

    for(int i = 0, last = 0; i < sz(pot); i++) {
        int k = create((1<<pot[i]));
        if(i > 0) {
            S_x.pb(k);
            S_y.pb(last);
        }
        if(i == sz(pot)-1) break;
        int add = pot[i+1] - pot[i] - !!i;
        while(add--) {
            S_y.pb(k);
            S_x.pb(-sz(S_y));
            k = -sz(S_x);
        }
        last = -sz(S_x);
    }

    int S = sz(S_x);
    ans.resize(M+1, -S);
    state.resize(S);
    for(int i = 0; i < S; i++)
        if(S_x[i] == -i-1) S_x[i] = -S;

    // for(int i = 0; i < S; i++)
    //     cout << S_x[i] << " " << S_y[i] << endl;

    dfs(-S, 0);

    for(int i = 0; i < S; i++) {
        if(S_x[i] >= 0) S_x[i] = A[S_x[i]];
        if(S_y[i] >= 0) S_y[i] = A[S_y[i]];
    }

    return answer(ans, S_x, S_y);
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 428 KB Output is correct
2 Correct 31 ms 5436 KB Output is correct
3 Correct 29 ms 5204 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 8 ms 1492 KB Output is correct
6 Execution timed out 1073 ms 3284 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 428 KB Output is correct
2 Correct 31 ms 5436 KB Output is correct
3 Correct 29 ms 5204 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 8 ms 1492 KB Output is correct
6 Execution timed out 1073 ms 3284 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 428 KB Output is correct
2 Correct 31 ms 5436 KB Output is correct
3 Correct 29 ms 5204 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 8 ms 1492 KB Output is correct
6 Execution timed out 1073 ms 3284 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 51 ms 6352 KB Output is correct
3 Correct 64 ms 6472 KB Output is correct
4 Runtime error 46 ms 10792 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 51 ms 6352 KB Output is correct
3 Correct 64 ms 6472 KB Output is correct
4 Runtime error 46 ms 10792 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -