oj.uz

Submission #856567

# Submission time Handle Problem Language Result Execution time Memory
856567 2023-10-04T01:29:33 Z sunwukong123 Mechanical Doll (IOI18_doll) C++14
100 / 100
 80 ms 15524 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 400005;
const int inf=1000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 
int k;
int n;
int msb(unsigned int n){
  return 1<<(32-__builtin_clz(n));
}
int cur=-1;
int X[MAXN], Y[MAXN], C[MAXN];
bool state[MAXN];
int I[MAXN];
int lim;
int dnc(int st, int en){

    int mi=(st+en)/2;
   
    int idx=cur--;
    if(st+1==en){
        if(!(st>lim)){
             X[-idx]=-1;
        } else{
            
        }

        return idx;
    } else{
        
        
        if(mi>lim){
            X[-idx]=dnc(st,mi);
        } else{
            X[-idx]=-1;
        }
        Y[-idx]=dnc(mi+1,en);
        return idx;
    }
    
}
void trav(int x, int next){

    if(state[-x]==0){
        state[-x]=!state[-x];
        if(X[-x]){
            trav(X[-x],next);
        } else{
            X[-x]=next;
        }

    } else{
        state[-x]=!state[-x];
        if(Y[-x]){
            trav(Y[-x],next);
        } else{
            Y[-x]=next;
        }
    }
}
void create_circuit(int M, vector<int> A) {

    n=A.size();

    k=msb(n);
    lim=k-n-1;


    dnc(0,k-1);

    C[0]=-1; // go to the first thing that i need to go
    for(int i=0;i<n;i++){
        C[A[i]]=-1;
        if(i==n-1)trav(-1,0);
        else trav(-1,A[i+1]);
    }
    
    vector<int> AA,AB,AC;
    AA=vector<int>(M+1,-1);
    AA[0]=A[0];
    int S=-cur;--S;
    AB=vector<int>(S);AC=vector<int>(S);
    for(int i=0;i<S;i++){
        AB[i]=X[i+1];
        AC[i]=Y[i+1];
    }

    answer(AA,AB,AC);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 28 ms 10196 KB Output is correct
3 Correct 27 ms 9816 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 9 ms 7772 KB Output is correct
6 Correct 40 ms 11612 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 28 ms 10196 KB Output is correct
3 Correct 27 ms 9816 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 9 ms 7772 KB Output is correct
6 Correct 40 ms 11612 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 51 ms 12380 KB Output is correct
9 Correct 55 ms 12628 KB Output is correct
10 Correct 80 ms 15524 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 28 ms 10196 KB Output is correct
3 Correct 27 ms 9816 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 9 ms 7772 KB Output is correct
6 Correct 40 ms 11612 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 51 ms 12380 KB Output is correct
9 Correct 55 ms 12628 KB Output is correct
10 Correct 80 ms 15524 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 76 ms 14916 KB Output is correct
15 Correct 47 ms 11868 KB Output is correct
16 Correct 74 ms 14920 KB Output is correct
17 Correct 1 ms 6488 KB Output is correct
18 Correct 1 ms 6488 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 78 ms 15176 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 42 ms 11344 KB Output is correct
3 Correct 45 ms 11316 KB Output is correct
4 Correct 74 ms 14164 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 42 ms 11344 KB Output is correct
3 Correct 45 ms 11316 KB Output is correct
4 Correct 74 ms 14164 KB Output is correct
5 Correct 73 ms 14160 KB Output is correct
6 Correct 74 ms 13904 KB Output is correct
7 Correct 79 ms 14164 KB Output is correct
8 Correct 75 ms 13808 KB Output is correct
9 Correct 45 ms 11484 KB Output is correct
10 Correct 71 ms 13904 KB Output is correct
11 Correct 71 ms 13908 KB Output is correct
12 Correct 45 ms 11344 KB Output is correct
13 Correct 46 ms 11608 KB Output is correct
14 Correct 47 ms 11472 KB Output is correct
15 Correct 49 ms 11732 KB Output is correct
16 Correct 2 ms 6744 KB Output is correct
17 Correct 42 ms 11352 KB Output is correct
18 Correct 45 ms 11348 KB Output is correct
19 Correct 49 ms 11696 KB Output is correct
20 Correct 71 ms 13904 KB Output is correct
21 Correct 73 ms 13792 KB Output is correct
22 Correct 70 ms 13780 KB Output is correct