oj.uz

Submission #856282

# Submission time Handle Problem Language Result Execution time Memory
856282 2023-10-03T03:48:55 Z sunwukong123 Mechanical Doll (IOI18_doll) C++14
37 / 100
 99 ms 14680 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 dnc(int st, int en){

    int mi=(st+en)/2;
   
    int idx=cur--;
    if(st+1==en){
        if(st>=n)X[-idx]=-1;
        if(en>=n)Y[-idx]=-1;
        return idx;
    } else{
        X[-idx]=dnc(st,mi);
        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();
    if(n==0){
        // do something.
        exit(0);
    }

    k=msb(n);

    dnc(0,k-1);
    Y[-(cur+1)]=0;

    C[0]=-1; // go to the first thing that i need to go
    trav(-1,A[0]);
    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);
    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
0 / 2.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4700 KB Output is partially correct
2 Partially correct 96 ms 13096 KB Output is partially correct
3 Partially correct 92 ms 13004 KB Output is partially correct
4 Partially correct 92 ms 14160 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4700 KB Output is partially correct
2 Partially correct 96 ms 13096 KB Output is partially correct
3 Partially correct 92 ms 13004 KB Output is partially correct
4 Partially correct 92 ms 14160 KB Output is partially correct
5 Partially correct 99 ms 14680 KB Output is partially correct
6 Partially correct 94 ms 14424 KB Output is partially correct
7 Partially correct 92 ms 14424 KB Output is partially correct
8 Partially correct 95 ms 14164 KB Output is partially correct
9 Partially correct 84 ms 13108 KB Output is partially correct
10 Partially correct 93 ms 14164 KB Output is partially correct
11 Partially correct 92 ms 14168 KB Output is partially correct
12 Partially correct 90 ms 12884 KB Output is partially correct
13 Partially correct 90 ms 13140 KB Output is partially correct
14 Partially correct 94 ms 13348 KB Output is partially correct
15 Partially correct 90 ms 13352 KB Output is partially correct
16 Partially correct 3 ms 4696 KB Output is partially correct
17 Correct 44 ms 9564 KB Output is correct
18 Partially correct 86 ms 12884 KB Output is partially correct
19 Partially correct 93 ms 12980 KB Output is partially correct
20 Partially correct 92 ms 14160 KB Output is partially correct
21 Partially correct 91 ms 14168 KB Output is partially correct
22 Partially correct 95 ms 14160 KB Output is partially correct