oj.uz

Submission #535426

# Submission time Handle Problem Language Result Execution time Memory
535426 2022-03-10T09:19:10 Z mario05092929 Mechanical Doll (IOI18_doll) C++14
100 / 100
 120 ms 19032 KB 
#include "doll.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair <int,int> pi;
typedef vector <int> vec;
typedef vector <ll> vecl;
using namespace std;
const int INF = 1e9;
int nam;
int c[1000005],g;
struct hap {int bit,wi,wh;};
vector <hap> sw;
int n,m,k;
int edge[1000005][2];

bool cmp(hap x,hap y) {
    return x.bit < y.bit;
}

void build(int x,int go,int bit) {
    if(!nam) return;
    c[x] = ++g;
    if(x*2 >= k) {
        edge[g][0] = edge[g][1] = -1;
        sw.push_back({bit,g,0});
        sw.push_back({bit+(1 << go),g,1});
        nam--;
        return;
    }
    build(x*2+1,go+1,bit+(1 << go)), build(x*2,go+1,bit);
    edge[c[x]][0] = (c[x*2] == -1 ? -1 : -c[x*2]);
    edge[c[x]][1] = (c[x*2+1] == -1 ? -1 :-c[x*2+1]);
}

void create_circuit(int M,vec A) {
    memset(c,-1,sizeof(c));
    n = A.size(), m = M;
    for(k = 1;k <= n;k *= 2);
    nam = n/2+1;
    build(1,0,0);
    sort(sw.begin(),sw.end(),cmp);
    for(int i = 0;i < n;i++) edge[sw[i].wi][sw[i].wh] = A[i];
    edge[sw.back().wi][sw.back().wh] = 0;
    vec le,ri;
    for(int i = 1;i <= g;i++) {
        le.push_back(edge[i][0]);
        ri.push_back(edge[i][1]);
    }
    answer(vector<int>(m+1,-1),le,ri);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 43 ms 9928 KB Output is correct
3 Correct 38 ms 9564 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 12 ms 4948 KB Output is correct
6 Correct 57 ms 12372 KB Output is correct
7 Correct 2 ms 4180 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 43 ms 9928 KB Output is correct
3 Correct 38 ms 9564 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 12 ms 4948 KB Output is correct
6 Correct 57 ms 12372 KB Output is correct
7 Correct 2 ms 4180 KB Output is correct
8 Correct 79 ms 13848 KB Output is correct
9 Correct 72 ms 14364 KB Output is correct
10 Correct 118 ms 19032 KB Output is correct
11 Correct 2 ms 4180 KB Output is correct
12 Correct 2 ms 4160 KB Output is correct
13 Correct 2 ms 4180 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 43 ms 9928 KB Output is correct
3 Correct 38 ms 9564 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 12 ms 4948 KB Output is correct
6 Correct 57 ms 12372 KB Output is correct
7 Correct 2 ms 4180 KB Output is correct
8 Correct 79 ms 13848 KB Output is correct
9 Correct 72 ms 14364 KB Output is correct
10 Correct 118 ms 19032 KB Output is correct
11 Correct 2 ms 4180 KB Output is correct
12 Correct 2 ms 4160 KB Output is correct
13 Correct 2 ms 4180 KB Output is correct
14 Correct 102 ms 18488 KB Output is correct
15 Correct 64 ms 13340 KB Output is correct
16 Correct 100 ms 18452 KB Output is correct
17 Correct 2 ms 4180 KB Output is correct
18 Correct 2 ms 4180 KB Output is correct
19 Correct 2 ms 4132 KB Output is correct
20 Correct 102 ms 18836 KB Output is correct
21 Correct 3 ms 4180 KB Output is correct
22 Correct 2 ms 4180 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 73 ms 12820 KB Output is correct
3 Correct 61 ms 12848 KB Output is correct
4 Correct 93 ms 17560 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 73 ms 12820 KB Output is correct
3 Correct 61 ms 12848 KB Output is correct
4 Correct 93 ms 17560 KB Output is correct
5 Correct 99 ms 18416 KB Output is correct
6 Correct 97 ms 18236 KB Output is correct
7 Correct 120 ms 18336 KB Output is correct
8 Correct 120 ms 18160 KB Output is correct
9 Correct 60 ms 12760 KB Output is correct
10 Correct 109 ms 18124 KB Output is correct
11 Correct 105 ms 17860 KB Output is correct
12 Correct 61 ms 13044 KB Output is correct
13 Correct 72 ms 13228 KB Output is correct
14 Correct 64 ms 13308 KB Output is correct
15 Correct 72 ms 13364 KB Output is correct
16 Correct 5 ms 4436 KB Output is correct
17 Correct 59 ms 13020 KB Output is correct
18 Correct 62 ms 12976 KB Output is correct
19 Correct 72 ms 13076 KB Output is correct
20 Correct 110 ms 18068 KB Output is correct
21 Correct 114 ms 17848 KB Output is correct
22 Correct 90 ms 17944 KB Output is correct