oj.uz

Submission #964081

# Submission time Handle Problem Language Result Execution time Memory
964081 2024-04-16T09:47:37 Z dong_gas Mechanical Doll (IOI18_doll) C++17
0 / 100
 1 ms 2648 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) {
        leaves.push_back({v,idx,0});
        r--;
        if(r) {
            leaves.push_back({v|(pivot<<1),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);
    nxt[num[N]][1]= num[2*N+1] ? -num[2*N+1] : -1;
}

void create_circuit(int M, vector<int> a) {
    m=M, n=a.size(), r=n+1;
    while((1<<h) < r) h++;

    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]=-1;
    }
    
    
    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 1 ms 2392 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2648 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB wrong motion
2 Halted 0 ms 0 KB -