oj.uz

Submission #611994

# Submission time Handle Problem Language Result Execution time Memory
611994 2022-07-29T09:46:25 Z krit3379 Mechanical Doll (IOI18_doll) C++17
53 / 100
 203 ms 32308 KB 
#include<bits/stdc++.h>
#include "doll.h"
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 500005

int l[N],r[N],sz,now;
bool sw[N];
vector<int> c,x,y,pos[N];
map<int,int> mp;

int bi(int x){
    int i=1;
    while(i<x)i<<=1;
    return i;
}

int bic(int x){
    int i=1,cnt=0;
    while(i<x)i<<=1,cnt++;
    return cnt;
}

int cre(int lev){
    int s=++sz;
    if(lev==1){
        l[s]=-1;
        r[s]=-1;
        return s;
    }
    l[s]=(cre(lev-1));
    r[s]=(cre(lev-1));
    return s;
}

void dfs(int s,int st,int head,vector<int> &a){
    if(now<=0)return ;
    if(!sw[s]){
        sw[s]^=1;
        if(l[s]==-1){
            int ps=pos[head].size();
            if(now<=ps)l[s]=-a[pos[head][ps-now]+1];
            else l[s]=st;
            now--;
            dfs(st,st,head,a);
        }
        else dfs(l[s],st,head,a);
    }
    else{
        sw[s]^=1;
        if(r[s]==-1){
            int ps=pos[head].size();
            if(now<=ps)r[s]=-a[pos[head][ps-now]+1];
            else r[s]=st;
            now--;
            dfs(st,st,head,a);
        }
        else dfs(r[s],st,head,a);
    }
}

void create_circuit(int m,vector<int> a){
    int i;
    c.resize(m+1);
    c[0]=a[0];
    i=0;
    for(auto x:a){
        mp[x]++;
        pos[x].push_back(i);
        i++;
    }
    a.push_back(0);
    for(auto [x,y]:mp){
        if(mp[x]==1)c[x]=a[pos[x][0]+1];
        else{
            now=bi(y);
            c[x]=-cre(bic(y));
            dfs(-c[x],-c[x],x,a);
        }
    }
    for(i=1;i<=sz;i++)x.push_back(-l[i]),y.push_back(-r[i]);
    answer(c,x,y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 60 ms 19280 KB Output is correct
3 Correct 52 ms 18984 KB Output is correct
4 Correct 8 ms 11988 KB Output is correct
5 Correct 20 ms 13224 KB Output is correct
6 Correct 119 ms 22704 KB Output is correct
7 Correct 7 ms 12060 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 60 ms 19280 KB Output is correct
3 Correct 52 ms 18984 KB Output is correct
4 Correct 8 ms 11988 KB Output is correct
5 Correct 20 ms 13224 KB Output is correct
6 Correct 119 ms 22704 KB Output is correct
7 Correct 7 ms 12060 KB Output is correct
8 Correct 104 ms 22744 KB Output is correct
9 Correct 154 ms 23976 KB Output is correct
10 Correct 203 ms 28284 KB Output is correct
11 Correct 8 ms 11988 KB Output is correct
12 Correct 6 ms 12060 KB Output is correct
13 Correct 7 ms 11988 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 60 ms 19280 KB Output is correct
3 Correct 52 ms 18984 KB Output is correct
4 Correct 8 ms 11988 KB Output is correct
5 Correct 20 ms 13224 KB Output is correct
6 Correct 119 ms 22704 KB Output is correct
7 Correct 7 ms 12060 KB Output is correct
8 Correct 104 ms 22744 KB Output is correct
9 Correct 154 ms 23976 KB Output is correct
10 Correct 203 ms 28284 KB Output is correct
11 Correct 8 ms 11988 KB Output is correct
12 Correct 6 ms 12060 KB Output is correct
13 Correct 7 ms 11988 KB Output is correct
14 Correct 146 ms 29380 KB Output is correct
15 Correct 81 ms 21236 KB Output is correct
16 Correct 115 ms 25380 KB Output is correct
17 Correct 6 ms 11988 KB Output is correct
18 Correct 6 ms 11988 KB Output is correct
19 Correct 8 ms 12052 KB Output is correct
20 Correct 162 ms 28244 KB Output is correct
21 Correct 6 ms 11988 KB Output is correct
22 Correct 6 ms 11996 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11988 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 7 ms 11988 KB Output is partially correct
2 Correct 61 ms 19724 KB Output is correct
3 Partially correct 132 ms 23152 KB Output is partially correct
4 Partially correct 115 ms 25048 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 7 ms 11988 KB Output is partially correct
2 Correct 61 ms 19724 KB Output is correct
3 Partially correct 132 ms 23152 KB Output is partially correct
4 Partially correct 115 ms 25048 KB Output is partially correct
5 Partially correct 158 ms 30960 KB Output is partially correct
6 Partially correct 164 ms 31924 KB Output is partially correct
7 Partially correct 139 ms 31692 KB Output is partially correct
8 Partially correct 161 ms 32196 KB Output is partially correct
9 Partially correct 103 ms 23500 KB Output is partially correct
10 Partially correct 162 ms 31592 KB Output is partially correct
11 Partially correct 132 ms 32308 KB Output is partially correct
12 Partially correct 90 ms 25216 KB Output is partially correct
13 Partially correct 86 ms 24380 KB Output is partially correct
14 Partially correct 88 ms 24148 KB Output is partially correct
15 Partially correct 98 ms 23884 KB Output is partially correct
16 Partially correct 8 ms 12372 KB Output is partially correct
17 Partially correct 69 ms 21988 KB Output is partially correct
18 Partially correct 70 ms 21960 KB Output is partially correct
19 Partially correct 91 ms 22932 KB Output is partially correct
20 Partially correct 106 ms 26756 KB Output is partially correct
21 Partially correct 112 ms 29720 KB Output is partially correct
22 Partially correct 89 ms 25672 KB Output is partially correct