oj.uz

Submission #320981

# Submission time Handle Problem Language Result Execution time Memory
320981 2020-11-10T12:01:28 Z mhy908 Mechanical Doll (IOI18_doll) C++14
16 / 100
 117 ms 21820 KB 
#include "doll.h"
#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(all(x))
#define press(x) x.erase(unique(all(x)), x.end());
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
typedef pair<LL, LL> pll;
const int INF=1e9;
const LL LLINF=1e18;

int n, m, arr[200010], cnt[100010], num[200010];
vector<int> vc[100010], ret1, ret2, ret3;
int conn[100010], re, sp[30][200010];
pii sw[200010];

void make_tree(int nw, int k, int nwnum, int rt, int skp, int lg, int tot, int c){
    if(k==2){
        int l=sp[lg][nwnum], r=sp[lg][nwnum+1];
        if(l<=skp)sw[nw].F=rt;
        else sw[nw].F=vc[c][l-skp-1];
        if(r<=skp)sw[nw].S=rt;
        else sw[nw].S=vc[c][r-skp-1];
        return;
    }
    re+=2;
    sw[nw]=mp(-re+1, -re);
    make_tree(-sw[nw].F, k/2, nwnum, rt, skp, lg, tot, c);
    make_tree(-sw[nw].S, k/2, nwnum+k/2, rt, skp, lg, tot, c);
}

void create_circuit(int M, vector<int> A){
    n=A.size(); m=M;
    for(int i=0; i<n; i++)arr[i+1]=A[i];
    for(int i=1; i<=n; i++){
        num[i]=++cnt[arr[i]];
        if(i!=n)vc[arr[i]].eb(arr[i+1]);
        else vc[arr[i]].eb(0);
    }
    sp[0][1]=1;
    for(int j=1; j<20; j++){
        for(int i=1; i<=(1<<j); i+=2)sp[j][i]=sp[j-1][(i+1)/2];
        for(int i=2; i<=(1<<j); i+=2)sp[j][i]=sp[j][i-1]+(1<<(j-1));
    }
    conn[0]=arr[1];
    for(int i=1; i<=m; i++){
        if(!cnt[i])continue;
        if(cnt[i]==1){
            conn[i]=vc[i][0];
            continue;
        }
        int sz, lg;
        for(sz=1, lg=0; sz<cnt[i]; sz*=2, lg++);
        ++re;
        conn[i]=-re;
        make_tree(re, sz, 1, -re, sz-cnt[i], lg, sz, i);
    }
    for(int i=0; i<=m; i++)ret1.eb(conn[i]);
    for(int i=1; i<=re; i++)ret2.eb(sw[i].F);
    for(int i=1; i<=re; i++)ret3.eb(sw[i].S);
    answer(ret1, ret2, ret3);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6604 KB Output is correct
2 Correct 45 ms 11776 KB Output is correct
3 Correct 40 ms 11048 KB Output is correct
4 Correct 6 ms 6604 KB Output is correct
5 Correct 20 ms 7976 KB Output is correct
6 Correct 57 ms 13388 KB Output is correct
7 Correct 7 ms 6524 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6604 KB Output is correct
2 Correct 45 ms 11776 KB Output is correct
3 Correct 40 ms 11048 KB Output is correct
4 Correct 6 ms 6604 KB Output is correct
5 Correct 20 ms 7976 KB Output is correct
6 Correct 57 ms 13388 KB Output is correct
7 Correct 7 ms 6524 KB Output is correct
8 Correct 65 ms 14944 KB Output is correct
9 Correct 71 ms 14904 KB Output is correct
10 Correct 117 ms 18132 KB Output is correct
11 Correct 6 ms 6604 KB Output is correct
12 Correct 7 ms 6596 KB Output is correct
13 Correct 7 ms 6604 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6604 KB Output is correct
2 Correct 45 ms 11776 KB Output is correct
3 Correct 40 ms 11048 KB Output is correct
4 Correct 6 ms 6604 KB Output is correct
5 Correct 20 ms 7976 KB Output is correct
6 Correct 57 ms 13388 KB Output is correct
7 Correct 7 ms 6524 KB Output is correct
8 Correct 65 ms 14944 KB Output is correct
9 Correct 71 ms 14904 KB Output is correct
10 Correct 117 ms 18132 KB Output is correct
11 Correct 6 ms 6604 KB Output is correct
12 Correct 7 ms 6596 KB Output is correct
13 Correct 7 ms 6604 KB Output is correct
14 Correct 111 ms 20228 KB Output is correct
15 Correct 61 ms 13472 KB Output is correct
16 Correct 101 ms 17268 KB Output is correct
17 Correct 5 ms 6604 KB Output is correct
18 Correct 8 ms 6580 KB Output is correct
19 Correct 9 ms 6596 KB Output is correct
20 Correct 112 ms 19040 KB Output is correct
21 Correct 7 ms 6604 KB Output is correct
22 Correct 5 ms 6604 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 6604 KB Output is partially correct
2 Correct 53 ms 13432 KB Output is correct
3 Runtime error 54 ms 21820 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 6604 KB Output is partially correct
2 Correct 53 ms 13432 KB Output is correct
3 Runtime error 54 ms 21820 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -