oj.uz

Submission #605212

# Submission time Handle Problem Language Result Execution time Memory
605212 2022-07-25T14:05:21 Z StrawHatWess Mechanical Doll (IOI18_doll) C++17
53 / 100
 886 ms 73180 KB 
#include "doll.h"

#include <bits/stdc++.h>
using namespace std;

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

typedef pair<int,int>pi; 
#define fi first
#define se second
typedef vector<pi>vpi; 
#define eb emplace_back

#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--)

void ckmax(ll &x, ll y){x=max(x,y);}
void ckmin(ll &x, ll y){x=min(x,y);}
//--------------------

const int MX=4e5+10; 
const int INF=1e9; 

int M,N; 
vi adj[MX]; 

int cnt=0; //counter for the next switch

unordered_map<int,int>mpX,mpY,st; 
void build(int u, int val){
    //st[u]=0; 

    if(val==1) return; 

    mpX[u]=--cnt;
    mpY[u]=--cnt;

    build(mpX[u],val/2); 
    build(mpY[u],val/2); 
}


void add(int x, int u, int val){
    if(val==1){
        if(!mpX.count(u)) mpX[u]=x; 
        else mpY[u]=x; 
        return; 
    }

    if(!st[u]) add(x,mpX[u],val/2); 
    else add(x,mpY[u],val/2); 

    st[u]^=1; 
}

void solve(){
    vi C(M+1); 

    FOR(i,0,M+1){
        if(!sz(adj[i])) C[i]=0; 
        else if(sz(adj[i])==1) C[i]=adj[i][0];
        else{
            int n=1; 
            while(n<sz(adj[i])) n*=2;

            C[i]=--cnt; 
            build(C[i],n/2); 


            vi vec; 
            FOR(rep,0,n-sz(adj[i])) vec.pb(C[i]); 
            for(int x: adj[i]) vec.pb(x);
            for(int x: vec) add(x,C[i],n/2); 
        }
    }   

    cnt*=-1; 
    vi X(cnt,-INF), Y(cnt,-INF); 
    for(auto it: mpX){
        int u=it.fi, x=it.se;
        u=-u; u--; 
        X[u]=x; 
    }
    for(auto it: mpY){
        int u=it.fi, x=it.se;
        u=-u; u--; 
        Y[u]=x; 
    }

    answer(C,X,Y); 

}

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

    adj[0].pb(A[0]); 

    FOR(i,0,N-1){
        adj[A[i]].pb(A[i+1]); 
    } 

    adj[A[N-1]].pb(0);


    solve(); 
}

/*

2 16
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2


*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 33 ms 13420 KB Output is correct
3 Correct 25 ms 13012 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 13 ms 10836 KB Output is correct
6 Correct 34 ms 14704 KB Output is correct
7 Correct 5 ms 9612 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 33 ms 13420 KB Output is correct
3 Correct 25 ms 13012 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 13 ms 10836 KB Output is correct
6 Correct 34 ms 14704 KB Output is correct
7 Correct 5 ms 9612 KB Output is correct
8 Correct 63 ms 20916 KB Output is correct
9 Correct 64 ms 19588 KB Output is correct
10 Correct 102 ms 27472 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 33 ms 13420 KB Output is correct
3 Correct 25 ms 13012 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 13 ms 10836 KB Output is correct
6 Correct 34 ms 14704 KB Output is correct
7 Correct 5 ms 9612 KB Output is correct
8 Correct 63 ms 20916 KB Output is correct
9 Correct 64 ms 19588 KB Output is correct
10 Correct 102 ms 27472 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 158 ms 41608 KB Output is correct
15 Correct 84 ms 25368 KB Output is correct
16 Correct 128 ms 32520 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 5 ms 9684 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 135 ms 33276 KB Output is correct
21 Correct 5 ms 9684 KB Output is correct
22 Correct 5 ms 9684 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 9684 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 4 ms 9684 KB Output is partially correct
2 Correct 331 ms 28552 KB Output is correct
3 Partially correct 886 ms 46844 KB Output is partially correct
4 Partially correct 875 ms 48776 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 9684 KB Output is partially correct
2 Correct 331 ms 28552 KB Output is correct
3 Partially correct 886 ms 46844 KB Output is partially correct
4 Partially correct 875 ms 48776 KB Output is partially correct
5 Partially correct 222 ms 53128 KB Output is partially correct
6 Partially correct 268 ms 59300 KB Output is partially correct
7 Partially correct 266 ms 57360 KB Output is partially correct
8 Partially correct 354 ms 70460 KB Output is partially correct
9 Partially correct 665 ms 48612 KB Output is partially correct
10 Partially correct 726 ms 70676 KB Output is partially correct
11 Partially correct 458 ms 73180 KB Output is partially correct
12 Partially correct 276 ms 48920 KB Output is partially correct
13 Partially correct 186 ms 44420 KB Output is partially correct
14 Partially correct 174 ms 43044 KB Output is partially correct
15 Partially correct 156 ms 39840 KB Output is partially correct
16 Partially correct 10 ms 10580 KB Output is partially correct
17 Partially correct 202 ms 41692 KB Output is partially correct
18 Partially correct 229 ms 41712 KB Output is partially correct
19 Partially correct 237 ms 43768 KB Output is partially correct
20 Partially correct 258 ms 50736 KB Output is partially correct
21 Partially correct 377 ms 59328 KB Output is partially correct
22 Partially correct 257 ms 48940 KB Output is partially correct