oj.uz

Submission #431767

# Submission time Handle Problem Language Result Execution time Memory
431767 2021-06-17T15:12:29 Z AmineWeslati Mechanical Doll (IOI18_doll) C++14
53 / 100
 214 ms 38924 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define all(x) begin(x),end(x)
#define sz(v) (int)v.size()

#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)
//------------------------------------------

const int MX=1e6;


int cnt=0; 

vi ans(MX),lft(MX,-1),rgt(MX,-1),par(MX);

int n,root; 
void build(int u, int nb=1){
    if(nb*2>=n) return; 


    lft[u]=++cnt; 
    rgt[u]=++cnt; 
    par[lft[u]]=u; 
    par[rgt[u]]=u; 

    build(lft[u],nb*2);
    build(rgt[u],nb*2);
}


vi st(MX,0);
int last=0;

vi vis_lft(MX,0),vis_rgt(MX,0);

int power(int x){
    bitset<32>b(x);
    int ans=0;
    FOR(i,0,32) ans+=b[i];
    return (ans==1);
}


void dfs(int u, int x){
    st[u]^=1;
    if(st[u]){
        if(lft[u]==-1){
            lft[u]=x; 
            vis_lft[u]=1;
        }
        else{
            dfs(lft[u],x);
        }
    }  
    else{
        if(rgt[u]==-1){
            if(last){
                //cout << u << endl;
                if(u!=cnt){
                    rgt[u]=root; 
                    dfs(root,x);
                }
                else vis_rgt[u]=1,rgt[u]=x; 
            }
            else{
                vis_rgt[u]=1;
                rgt[u]=x; 
            }
        }
        else{
            dfs(rgt[u],x);
        }
    }
    
}

void create_circuit(int M, vi a) {
    int N=sz(a);

    vi adj[M+1];
    adj[0].pb(a[0]);
    FOR(i,0,N){
        if(i==N-1) adj[a[i]].pb(0);
        else adj[a[i]].pb(a[i+1]);
    }


    FOR(i,0,M+1) if(sz(adj[i])){
        n=sz(adj[i]);

        if(n==1){
            ans[i]=adj[i][0];
            continue;
        }

        ++cnt; 
        root=cnt; 
        ans[i]=-root; 
        
        build(root);

        FOR(j,0,n){
            int x=adj[i][j];
            last=(j==n-1);
            dfs(root,x);
        }
    }

    /*FOR(i,1,cnt+1) if(vis_lft[i]){
        cout << lft[i] << ' ' << rgt[i];
        cout << endl;
    }*/

    ans.resize(M+1);
    lft.erase(lft.begin()); lft.resize(cnt); 

    

    FOR(i,0,cnt){
        int &x=lft[i];
        if(!vis_lft[i+1]) x=-x;
    }

    rgt.erase(rgt.begin()); rgt.resize(cnt); 
    FOR(i,0,cnt){
        int &x=rgt[i];
        if(!vis_rgt[i+1]) x=-x;
    }

    /*FOR(i,0,M+1) cout << ans[i] << ' ';
    cout << endl;*/
    /*for(auto x: lft) cout << x << ' ';
    cout << endl;
    for(auto x: rgt) cout << x << ' ';
    cout << endl;*/

    /*for(int x: lft) cout << x << ' ';
    cout << endl; */
    answer(ans,lft,rgt);
}


/*

4 4
1 2 1 3

*/
/*


1 5
1 1 1 1 1

*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 27608 KB Output is correct
2 Correct 49 ms 33400 KB Output is correct
3 Correct 46 ms 32340 KB Output is correct
4 Correct 17 ms 27596 KB Output is correct
5 Correct 29 ms 30776 KB Output is correct
6 Correct 61 ms 34844 KB Output is correct
7 Correct 18 ms 27684 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 27608 KB Output is correct
2 Correct 49 ms 33400 KB Output is correct
3 Correct 46 ms 32340 KB Output is correct
4 Correct 17 ms 27596 KB Output is correct
5 Correct 29 ms 30776 KB Output is correct
6 Correct 61 ms 34844 KB Output is correct
7 Correct 18 ms 27684 KB Output is correct
8 Correct 84 ms 33916 KB Output is correct
9 Correct 77 ms 35344 KB Output is correct
10 Correct 113 ms 37192 KB Output is correct
11 Correct 18 ms 27692 KB Output is correct
12 Correct 19 ms 27656 KB Output is correct
13 Correct 20 ms 27664 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 27608 KB Output is correct
2 Correct 49 ms 33400 KB Output is correct
3 Correct 46 ms 32340 KB Output is correct
4 Correct 17 ms 27596 KB Output is correct
5 Correct 29 ms 30776 KB Output is correct
6 Correct 61 ms 34844 KB Output is correct
7 Correct 18 ms 27684 KB Output is correct
8 Correct 84 ms 33916 KB Output is correct
9 Correct 77 ms 35344 KB Output is correct
10 Correct 113 ms 37192 KB Output is correct
11 Correct 18 ms 27692 KB Output is correct
12 Correct 19 ms 27656 KB Output is correct
13 Correct 20 ms 27664 KB Output is correct
14 Correct 130 ms 37256 KB Output is correct
15 Correct 71 ms 32360 KB Output is correct
16 Correct 114 ms 34944 KB Output is correct
17 Correct 17 ms 27644 KB Output is correct
18 Correct 18 ms 27608 KB Output is correct
19 Correct 17 ms 27708 KB Output is correct
20 Correct 113 ms 36832 KB Output is correct
21 Correct 21 ms 27708 KB Output is correct
22 Correct 18 ms 27596 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 27704 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 17 ms 27656 KB Output is partially correct
2 Correct 107 ms 31424 KB Output is correct
3 Partially correct 213 ms 33500 KB Output is partially correct
4 Partially correct 181 ms 34360 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 17 ms 27656 KB Output is partially correct
2 Correct 107 ms 31424 KB Output is correct
3 Partially correct 213 ms 33500 KB Output is partially correct
4 Partially correct 181 ms 34360 KB Output is partially correct
5 Partially correct 155 ms 38368 KB Output is partially correct
6 Partially correct 141 ms 38788 KB Output is partially correct
7 Partially correct 156 ms 38576 KB Output is partially correct
8 Partially correct 145 ms 38844 KB Output is partially correct
9 Partially correct 154 ms 33692 KB Output is partially correct
10 Partially correct 214 ms 37828 KB Output is partially correct
11 Partially correct 179 ms 38924 KB Output is partially correct
12 Partially correct 121 ms 35028 KB Output is partially correct
13 Partially correct 121 ms 34864 KB Output is partially correct
14 Partially correct 96 ms 34748 KB Output is partially correct
15 Partially correct 101 ms 34724 KB Output is partially correct
16 Partially correct 18 ms 27912 KB Output is partially correct
17 Partially correct 88 ms 33412 KB Output is partially correct
18 Partially correct 94 ms 33332 KB Output is partially correct
19 Partially correct 92 ms 33732 KB Output is partially correct
20 Partially correct 127 ms 35588 KB Output is partially correct
21 Partially correct 140 ms 37232 KB Output is partially correct
22 Partially correct 133 ms 34932 KB Output is partially correct