oj.uz

Submission #995448

# Submission time Handle Problem Language Result Execution time Memory
995448 2024-06-09T06:09:01 Z hirayuu_oj Mechanical Doll (IOI18_doll) C++17
100 / 100
 103 ms 12116 KB 
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
ll LINF=(1LL<<61)-1;
ll MINF=1LL<<40;
int INF=INT_MAX>>1;

#include "doll.h"

template<class S>
void out_vector(vector<S> v){
    for(S i:v)cerr<<i<<" ";
    cerr<<"\n";
}

vector<int> X,Y;
int make(int x,int y){
    if(y==0)return -1;
    if(x==1)return 0;
    X.emplace_back(0);
    Y.emplace_back(0);
    int ret=X.size();
    int ri=make(x/2,min(y,x/2));
    int lf=make(x/2,max(0,y-x/2));
    X[ret-1]=lf;
    Y[ret-1]=ri;
    return -ret;
}
void create_circuit(int M, std::vector<int> A) {
    int N=A.size();
    A.emplace_back(0);
    vector<int> C(M+1,-1);
    C[0]=A[0];
    int ceil=1;
    while(ceil<N)ceil<<=1;
    make(ceil,N);
    if(N==1){
        X={-1};
        Y={0};
    }
    int S=X.size();
    vector<int> cond(S,0);
    vector<pair<int,int>> order;
    rep(i,N){
        int pos=-1;
        while(true){
            if(cond[-pos-1]==0){
                cond[-pos-1]=1;
                if(X[-pos-1]==0){
                    order.emplace_back(pos,0);
                    break;
                }
                else{
                    pos=X[-pos-1];
                }
            }
            else{
                cond[-pos-1]=0;
                if(Y[-pos-1]==0){
                    order.emplace_back(pos,1);
                    break;
                }
                else{
                    pos=Y[-pos-1];
                }
            }
        }
    }
    rep(i,N){
        if(order[i].second==0){
            X[-order[i].first-1]=A[i+1];
        }
        else{
            Y[-order[i].first-1]=A[i+1];
        }
    }
    answer(C,X,Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 28 ms 4960 KB Output is correct
3 Correct 30 ms 4952 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 1372 KB Output is correct
6 Correct 46 ms 6936 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 1 ms 344 KB Output is correct
2 Correct 28 ms 4960 KB Output is correct
3 Correct 30 ms 4952 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 1372 KB Output is correct
6 Correct 46 ms 6936 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 56 ms 8004 KB Output is correct
9 Correct 59 ms 8600 KB Output is correct
10 Correct 85 ms 12116 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 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 1 ms 344 KB Output is correct
2 Correct 28 ms 4960 KB Output is correct
3 Correct 30 ms 4952 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 1372 KB Output is correct
6 Correct 46 ms 6936 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 56 ms 8004 KB Output is correct
9 Correct 59 ms 8600 KB Output is correct
10 Correct 85 ms 12116 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 90 ms 11688 KB Output is correct
15 Correct 65 ms 7404 KB Output is correct
16 Correct 87 ms 11536 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 87 ms 11792 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 344 KB Output is correct

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 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 436 KB Output is correct
2 Correct 49 ms 7128 KB Output is correct
3 Correct 56 ms 6896 KB Output is correct
4 Correct 81 ms 10300 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 436 KB Output is correct
2 Correct 49 ms 7128 KB Output is correct
3 Correct 56 ms 6896 KB Output is correct
4 Correct 81 ms 10300 KB Output is correct
5 Correct 103 ms 11280 KB Output is correct
6 Correct 88 ms 11016 KB Output is correct
7 Correct 82 ms 11024 KB Output is correct
8 Correct 87 ms 10716 KB Output is correct
9 Correct 53 ms 6916 KB Output is correct
10 Correct 86 ms 10564 KB Output is correct
11 Correct 81 ms 10352 KB Output is correct
12 Correct 53 ms 6916 KB Output is correct
13 Correct 51 ms 7496 KB Output is correct
14 Correct 57 ms 7224 KB Output is correct
15 Correct 56 ms 7404 KB Output is correct
16 Correct 2 ms 600 KB Output is correct
17 Correct 49 ms 7232 KB Output is correct
18 Correct 50 ms 7244 KB Output is correct
19 Correct 54 ms 6892 KB Output is correct
20 Correct 82 ms 10504 KB Output is correct
21 Correct 80 ms 10300 KB Output is correct
22 Correct 97 ms 10300 KB Output is correct