oj.uz

Submission #964107

# Submission time Handle Problem Language Result Execution time Memory
964107 2024-04-16T10:31:57 Z dong_gas Mechanical Doll (IOI18_doll) C++17
0 / 100
 2 ms 4704 KB 
#pragma GCC optimize("O3", "Ofast", "unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/extc++.h>
#include "doll.h"
#define all(v) v.begin(), v.end()
#define zip(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int n, m, idx, r, h;
int num[400040], nxt[400040][2];
vector<tuple<int,int,int>> leaves;

void go(int N, int depth, int v) {
    if(!r) return;
    if(depth>h) return;
    //v: 순서
    int pivot=1<<depth;
    num[N]=++idx;
    if(depth+1==h) {
        nxt[idx][0]=nxt[idx][1]=-1;
        leaves.push_back({v,idx,0});
        leaves.push_back({v|pivot,idx,1});
        r--;
        return;
    }
    go(2*N,depth+1,v);
    nxt[num[N]][0]= num[2*N] ? -num[2*N] : -1;
    go(2*N+1,depth+1,v|pivot);
    //if(num[N]==5) cout<<num[2*N+1]<<endl;
    nxt[num[N]][1]= num[2*N+1] ? -num[2*N+1] : -1;
    //cout<<num[N]<<' '<<nxt[num[N]][0]<<' '<<nxt[num[N]][1]<<endl;
}

void create_circuit(int M, vector<int> a) {
    m=M, n=a.size(), r=n+1;
    while((1<<h) < r) h++;
    //cout<<h<<endl;
    r=n/2+1;
    memset(nxt,-1,sizeof(nxt));
    //memset(num,-1,sizeof(num));
    go(1,0,0);
    sort(all(leaves));
    
    for(int i=0;i<=n;i++) {
        auto [o, k, dir] = leaves[i];
        //cout<<o<<' '<<k<<' '<<dir<<endl;
        if(i<n) nxt[k][dir]=a[i];
        else nxt[k][dir]=0;
    }
    
    
    vector<int> c(m+1,-1), x(idx), y(idx);
    for(int i=0;i<idx;i++) x[i]=nxt[i+1][0], y[i]=nxt[i+1][1];
    answer(c,x,y);

}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4536 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4536 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4536 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4704 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4700 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4700 KB state 'Y'
2 Halted 0 ms 0 KB -