oj.uz

Submission #964127

# Submission time Handle Problem Language Result Execution time Memory
964127 2024-04-16T10:49:30 Z dong_gas Mechanical Doll (IOI18_doll) C++17
100 / 100
 98 ms 18608 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+1,depth+1,v|pivot);
    nxt[num[N]][1]= num[2*N+1] ? -num[2*N+1] : -1;
    go(2*N,depth+1,v);
    nxt[num[N]][0]= num[2*N] ? -num[2*N] : -1;
    
    //cout<<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++;
    memset(nxt,-1,sizeof(nxt));
    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);
    //for(int xx: x) cout<<xx<<' ';
    //cout<<endl;
    //for(int xx: y) cout<<xx<<' ';
    //cout<<endl;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 29 ms 9920 KB Output is correct
3 Correct 28 ms 9432 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 8 ms 5820 KB Output is correct
6 Correct 48 ms 11960 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 29 ms 9920 KB Output is correct
3 Correct 28 ms 9432 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 8 ms 5820 KB Output is correct
6 Correct 48 ms 11960 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 51 ms 13196 KB Output is correct
9 Correct 53 ms 13772 KB Output is correct
10 Correct 88 ms 18608 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 2 ms 4540 KB Output is correct
13 Correct 1 ms 4700 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 29 ms 9920 KB Output is correct
3 Correct 28 ms 9432 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 8 ms 5820 KB Output is correct
6 Correct 48 ms 11960 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 51 ms 13196 KB Output is correct
9 Correct 53 ms 13772 KB Output is correct
10 Correct 88 ms 18608 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 2 ms 4540 KB Output is correct
13 Correct 1 ms 4700 KB Output is correct
14 Correct 82 ms 17548 KB Output is correct
15 Correct 57 ms 13516 KB Output is correct
16 Correct 79 ms 17324 KB Output is correct
17 Correct 1 ms 4696 KB Output is correct
18 Correct 1 ms 4700 KB Output is correct
19 Correct 1 ms 4700 KB Output is correct
20 Correct 98 ms 17664 KB Output is correct
21 Correct 1 ms 4700 KB Output is correct
22 Correct 1 ms 4700 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4540 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 1 ms 4696 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 46 ms 11916 KB Output is correct
3 Correct 50 ms 11972 KB Output is correct
4 Correct 81 ms 15648 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 46 ms 11916 KB Output is correct
3 Correct 50 ms 11972 KB Output is correct
4 Correct 81 ms 15648 KB Output is correct
5 Correct 79 ms 17076 KB Output is correct
6 Correct 81 ms 16916 KB Output is correct
7 Correct 80 ms 16860 KB Output is correct
8 Correct 75 ms 16564 KB Output is correct
9 Correct 42 ms 13244 KB Output is correct
10 Correct 72 ms 16364 KB Output is correct
11 Correct 73 ms 16100 KB Output is correct
12 Correct 53 ms 13124 KB Output is correct
13 Correct 51 ms 13244 KB Output is correct
14 Correct 48 ms 12636 KB Output is correct
15 Correct 56 ms 12736 KB Output is correct
16 Correct 2 ms 4956 KB Output is correct
17 Correct 45 ms 12184 KB Output is correct
18 Correct 45 ms 12060 KB Output is correct
19 Correct 47 ms 13616 KB Output is correct
20 Correct 73 ms 16340 KB Output is correct
21 Correct 75 ms 16088 KB Output is correct
22 Correct 89 ms 16100 KB Output is correct