oj.uz

Submission #612543

# Submission time Handle Problem Language Result Execution time Memory
612543 2022-07-29T17:15:08 Z krit3379 Mechanical Doll (IOI18_doll) C++17
100 / 100
 212 ms 36460 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 t[4*N],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 lbi(int x){
    if(x==0)return 0;
    return 1<<(31-__builtin_clz(x));
}

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

void cre(int x,int l,int r,int cnt){
    if(l==r){t[x]=l>cnt;return ;}
    int mid=(l+r)/2;
    cre(x*2,l,mid,cnt);
    cre(x*2+1,mid+1,r,cnt);
    t[x]=t[x*2]+t[x*2+1];
}

void sol(int x,int l,int r){
    mp[x];
    if(l+1==r){
        if(!t[x*2])L[x]=1;
        return ;
    }
    int mid=(l+r)/2;
    if(!t[x*2])L[x]=1;
    else L[x]=x*2,sol(x*2,l,mid);
    R[x]=x*2+1;
    sol(x*2+1,mid+1,r);
}

void dfs(int s,vector<int> &a){
    if(now>=a.size())return ;
    if(!sw[s]){
        sw[s]^=1;
        if(!L[s]){
            L[s]=-a[now++];
            dfs(1,a);
        }
        else dfs(L[s],a);
    }
    else{
        sw[s]^=1;
        if(!R[s]){
            R[s]=-a[now++];
            dfs(1,a);
        }
        else dfs(R[s],a);
    }
}

void create_circuit(int m,vector<int> a){
    int n,i;
    a.push_back(0);
    n=a.size();
    c.resize(m+1);
    for(i=0;i<=m;i++)c[i]=-1;
    cre(1,1,bi(n),bi(n)-n);
    sol(1,1,bi(n));
    dfs(1,a);
    for(auto &[x,y]:mp)y=--sz;
    for(auto [key,val]:mp){
        if(L[key]>0)x.push_back(mp[L[key]]);
        else x.push_back(-L[key]);
        if(R[key]>0)y.push_back(mp[R[key]]);
        else y.push_back(-R[key]);
    }
    answer(c,x,y);
}

Compilation message

doll.cpp: In function 'void dfs(int, std::vector<int>&)':
doll.cpp:52:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     if(now>=a.size())return ;
      |        ~~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 77 ms 21184 KB Output is correct
3 Correct 61 ms 21044 KB Output is correct
4 Correct 10 ms 12084 KB Output is correct
5 Correct 15 ms 13140 KB Output is correct
6 Correct 118 ms 25052 KB Output is correct
7 Correct 8 ms 11988 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 77 ms 21184 KB Output is correct
3 Correct 61 ms 21044 KB Output is correct
4 Correct 10 ms 12084 KB Output is correct
5 Correct 15 ms 13140 KB Output is correct
6 Correct 118 ms 25052 KB Output is correct
7 Correct 8 ms 11988 KB Output is correct
8 Correct 120 ms 28628 KB Output is correct
9 Correct 148 ms 29144 KB Output is correct
10 Correct 202 ms 36460 KB Output is correct
11 Correct 9 ms 11996 KB Output is correct
12 Correct 8 ms 11964 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 7 ms 11988 KB Output is correct
2 Correct 77 ms 21184 KB Output is correct
3 Correct 61 ms 21044 KB Output is correct
4 Correct 10 ms 12084 KB Output is correct
5 Correct 15 ms 13140 KB Output is correct
6 Correct 118 ms 25052 KB Output is correct
7 Correct 8 ms 11988 KB Output is correct
8 Correct 120 ms 28628 KB Output is correct
9 Correct 148 ms 29144 KB Output is correct
10 Correct 202 ms 36460 KB Output is correct
11 Correct 9 ms 11996 KB Output is correct
12 Correct 8 ms 11964 KB Output is correct
13 Correct 7 ms 11988 KB Output is correct
14 Correct 189 ms 35944 KB Output is correct
15 Correct 121 ms 28136 KB Output is correct
16 Correct 193 ms 35604 KB Output is correct
17 Correct 6 ms 11988 KB Output is correct
18 Correct 7 ms 12052 KB Output is correct
19 Correct 8 ms 11988 KB Output is correct
20 Correct 212 ms 36144 KB Output is correct
21 Correct 8 ms 12060 KB Output is correct
22 Correct 9 ms 11988 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11988 KB Output is correct
2 Correct 8 ms 12060 KB Output is correct
3 Correct 9 ms 12072 KB Output is correct
4 Correct 8 ms 11988 KB Output is correct
5 Correct 8 ms 12056 KB Output is correct
6 Correct 9 ms 12012 KB Output is correct
7 Correct 8 ms 12048 KB Output is correct
8 Correct 8 ms 12036 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12056 KB Output is correct
2 Correct 123 ms 27248 KB Output is correct
3 Correct 128 ms 27172 KB Output is correct
4 Correct 189 ms 33924 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12056 KB Output is correct
2 Correct 123 ms 27248 KB Output is correct
3 Correct 128 ms 27172 KB Output is correct
4 Correct 189 ms 33924 KB Output is correct
5 Correct 207 ms 35316 KB Output is correct
6 Correct 169 ms 35192 KB Output is correct
7 Correct 169 ms 35244 KB Output is correct
8 Correct 197 ms 34944 KB Output is correct
9 Correct 98 ms 27204 KB Output is correct
10 Correct 156 ms 34860 KB Output is correct
11 Correct 181 ms 34548 KB Output is correct
12 Correct 109 ms 27504 KB Output is correct
13 Correct 109 ms 27800 KB Output is correct
14 Correct 106 ms 27888 KB Output is correct
15 Correct 105 ms 28104 KB Output is correct
16 Correct 10 ms 12500 KB Output is correct
17 Correct 102 ms 26644 KB Output is correct
18 Correct 98 ms 27356 KB Output is correct
19 Correct 100 ms 27488 KB Output is correct
20 Correct 158 ms 34792 KB Output is correct
21 Correct 166 ms 34500 KB Output is correct
22 Correct 166 ms 34636 KB Output is correct