oj.uz

Submission #714137

# Submission time Handle Problem Language Result Execution time Memory
714137 2023-03-24T02:33:05 Z victor_gao Mechanical Doll (IOI18_doll) C++17
100 / 100
 131 ms 15088 KB 
#include "doll.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
vector<int>ans1,ans2,c,arr;
int n,m,now=0,vis[400015];
pii seg[400015];
int build(int l,int r,int root,int out){
    if (l==r)
        return -root;
    int mid=(l+r)>>1,use=--now;
    use=abs(use);
    if (out<(mid-l+1)){
        seg[use].x=build(l,mid,root,out);
        seg[use].y=build(mid+1,r,root,0);
    }
    else {
        out-=(mid-l+1);
        seg[use].x=root;
        seg[use].y=build(mid+1,r,root,out);
    }
    return use;
}
void dfs(int i,int order,int root){
    if (order==arr.size()) return;
    if (!vis[i]){
        vis[i]^=1;
        if (seg[i].x==-root)
            ans1[i]=arr[order++];
        else ans1[i]=-seg[i].x;
        dfs(abs(seg[i].x),order,root);
    }
    else {
        vis[i]^=1;
        if (seg[i].y==-root)
            ans2[i]=arr[order++];
        else ans2[i]=-seg[i].y;
        dfs(abs(seg[i].y),order,root);
    }
    return;
}
void create_circuit(int M, std::vector<int> A) {
    m=M;
    ans1.resize(400000); ans2.resize(400000);
    A.push_back(0);
    n = A.size(); arr=A;
    c.resize(m+1,-1);
    int p=__lg(n-1)+1;
    build(0,(1LL<<p)-1,1,(1LL<<p)-n);
    dfs(1,0,1);
    now=abs(now);
    vector<int>X,Y;
    for (int i=1;i<=now;i++){
        X.push_back(ans1[i]);
    }
    for (int i=1;i<=now;i++){
        Y.push_back(ans2[i]);
    }
    answer(c, X, Y);
}
/*
2 16
1 2 2 1 2 2 1 1 1 1 2 2 2 1 2 2 2 1 1 2 2 2 1
4 7
1 1 1 1 1 1 1 1 
./rand
./doll
*/

Compilation message

doll.cpp: In function 'void dfs(int, int, int)':
doll.cpp:27:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     if (order==arr.size()) return;
      |         ~~~~~^~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3412 KB Output is correct
2 Correct 41 ms 8024 KB Output is correct
3 Correct 37 ms 7876 KB Output is correct
4 Correct 2 ms 3376 KB Output is correct
5 Correct 10 ms 4528 KB Output is correct
6 Correct 56 ms 10152 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3412 KB Output is correct
2 Correct 41 ms 8024 KB Output is correct
3 Correct 37 ms 7876 KB Output is correct
4 Correct 2 ms 3376 KB Output is correct
5 Correct 10 ms 4528 KB Output is correct
6 Correct 56 ms 10152 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 68 ms 11208 KB Output is correct
9 Correct 79 ms 11684 KB Output is correct
10 Correct 131 ms 15088 KB Output is correct
11 Correct 2 ms 3412 KB Output is correct
12 Correct 2 ms 3380 KB Output is correct
13 Correct 2 ms 3412 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3412 KB Output is correct
2 Correct 41 ms 8024 KB Output is correct
3 Correct 37 ms 7876 KB Output is correct
4 Correct 2 ms 3376 KB Output is correct
5 Correct 10 ms 4528 KB Output is correct
6 Correct 56 ms 10152 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 68 ms 11208 KB Output is correct
9 Correct 79 ms 11684 KB Output is correct
10 Correct 131 ms 15088 KB Output is correct
11 Correct 2 ms 3412 KB Output is correct
12 Correct 2 ms 3380 KB Output is correct
13 Correct 2 ms 3412 KB Output is correct
14 Correct 115 ms 14724 KB Output is correct
15 Correct 76 ms 10660 KB Output is correct
16 Correct 109 ms 14292 KB Output is correct
17 Correct 2 ms 3412 KB Output is correct
18 Correct 2 ms 3412 KB Output is correct
19 Correct 2 ms 3412 KB Output is correct
20 Correct 102 ms 14860 KB Output is correct
21 Correct 2 ms 3376 KB Output is correct
22 Correct 2 ms 3412 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3380 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3380 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3464 KB Output is correct
8 Correct 2 ms 3384 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 81 ms 10096 KB Output is correct
3 Correct 68 ms 10252 KB Output is correct
4 Correct 107 ms 13272 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 81 ms 10096 KB Output is correct
3 Correct 68 ms 10252 KB Output is correct
4 Correct 107 ms 13272 KB Output is correct
5 Correct 106 ms 14212 KB Output is correct
6 Correct 95 ms 13868 KB Output is correct
7 Correct 122 ms 14040 KB Output is correct
8 Correct 110 ms 13640 KB Output is correct
9 Correct 78 ms 10132 KB Output is correct
10 Correct 100 ms 13588 KB Output is correct
11 Correct 99 ms 13336 KB Output is correct
12 Correct 68 ms 10096 KB Output is correct
13 Correct 67 ms 10424 KB Output is correct
14 Correct 72 ms 10428 KB Output is correct
15 Correct 67 ms 10616 KB Output is correct
16 Correct 4 ms 3668 KB Output is correct
17 Correct 73 ms 11544 KB Output is correct
18 Correct 70 ms 10124 KB Output is correct
19 Correct 68 ms 10132 KB Output is correct
20 Correct 103 ms 13412 KB Output is correct
21 Correct 99 ms 13416 KB Output is correct
22 Correct 96 ms 13348 KB Output is correct