oj.uz

Submission #714128

# Submission time Handle Problem Language Result Execution time Memory
714128 2023-03-24T02:10:57 Z victor_gao Mechanical Doll (IOI18_doll) C++17
85.553 / 100
 110 ms 26968 KB 
#include "doll.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
vector<int>to[200015],g[200015];
vector<int>ans1,ans2,c;
int n,m,now=0,vis[400015];
pii seg[400015];
int build(int num,int l,int r,int root,int out){
    if (l==r){
        if (out) return root;
        return -root;
    }
    int mid=(l+r)>>1,use=--now;
    use=abs(use);
    if (out<=(mid-l+1)){
        seg[use].x=build(num,l,mid,root,out);
        seg[use].y=build(num,mid+1,r,root,0);
    }
    else {
        out-=(mid-l+1);
        seg[use].x=root;
        seg[use].y=build(num,mid+1,r,root,out);
    }
    return use;
}
void dfs(int num,int i,int order,int root){
    if (order==g[num].size()) return;
    if (!vis[i]){
        vis[i]^=1;
        if (seg[i].x==-root)
            ans1[i]=g[num][order++];
        else ans1[i]=-seg[i].x;
        dfs(num,abs(seg[i].x),order,root);
    }
    else {
        vis[i]^=1;
        if (seg[i].y==-root)
            ans2[i]=g[num][order++];
        else ans2[i]=-seg[i].y;
        dfs(num,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();
    for (int i=0;i<n-1;i++){
        g[A[i]].push_back(A[i+1]);
    }
    c.resize(m+1);
    int now_root=0;
    for (int i=0;i<=m;i++){
        if (g[i].empty()) c[i]=0;
        else if (g[i].size()==1) c[i]=g[i][0];
        else {
            int p=__lg((int)(g[i].size()-1))+1;
            now_root=abs(now)+1;
            c[i]=-now_root;
            build(i,0,(1LL<<p)-1,now_root,(1LL<<p)-g[i].size());
            dfs(i,now_root,0,now_root);
        }
    }
    c[0]=A[0];
    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 5
1 2 1 3 1
./rand
./doll
*/

Compilation message

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 31 ms 16968 KB Output is correct
3 Correct 27 ms 16644 KB Output is correct
4 Correct 8 ms 12776 KB Output is correct
5 Correct 15 ms 13932 KB Output is correct
6 Correct 42 ms 18748 KB Output is correct
7 Correct 9 ms 12828 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 31 ms 16968 KB Output is correct
3 Correct 27 ms 16644 KB Output is correct
4 Correct 8 ms 12776 KB Output is correct
5 Correct 15 ms 13932 KB Output is correct
6 Correct 42 ms 18748 KB Output is correct
7 Correct 9 ms 12828 KB Output is correct
8 Correct 65 ms 20760 KB Output is correct
9 Correct 57 ms 20884 KB Output is correct
10 Correct 77 ms 24908 KB Output is correct
11 Correct 7 ms 12768 KB Output is correct
12 Correct 7 ms 12756 KB Output is correct
13 Correct 6 ms 12756 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 31 ms 16968 KB Output is correct
3 Correct 27 ms 16644 KB Output is correct
4 Correct 8 ms 12776 KB Output is correct
5 Correct 15 ms 13932 KB Output is correct
6 Correct 42 ms 18748 KB Output is correct
7 Correct 9 ms 12828 KB Output is correct
8 Correct 65 ms 20760 KB Output is correct
9 Correct 57 ms 20884 KB Output is correct
10 Correct 77 ms 24908 KB Output is correct
11 Correct 7 ms 12768 KB Output is correct
12 Correct 7 ms 12756 KB Output is correct
13 Correct 6 ms 12756 KB Output is correct
14 Correct 95 ms 26556 KB Output is correct
15 Correct 50 ms 20672 KB Output is correct
16 Correct 74 ms 23512 KB Output is correct
17 Correct 7 ms 12756 KB Output is correct
18 Correct 9 ms 12768 KB Output is correct
19 Correct 7 ms 12756 KB Output is correct
20 Correct 85 ms 24988 KB Output is correct
21 Correct 7 ms 12756 KB Output is correct
22 Correct 7 ms 12772 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12772 KB Output is correct
2 Correct 7 ms 12776 KB Output is correct
3 Correct 7 ms 12768 KB Output is correct
4 Correct 7 ms 12772 KB Output is correct
5 Correct 7 ms 12756 KB Output is correct
6 Correct 6 ms 12788 KB Output is correct
7 Correct 7 ms 12768 KB Output is correct
8 Correct 7 ms 12776 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12756 KB Output is correct
2 Correct 69 ms 21324 KB Output is correct
3 Correct 70 ms 19928 KB Output is correct
4 Correct 110 ms 23616 KB Output is correct

Subtask #6
41.5530038336 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12756 KB Output is correct
2 Correct 69 ms 21324 KB Output is correct
3 Correct 70 ms 19928 KB Output is correct
4 Correct 110 ms 23616 KB Output is correct
5 Partially correct 101 ms 26968 KB Output is partially correct
6 Partially correct 91 ms 26712 KB Output is partially correct
7 Partially correct 95 ms 26856 KB Output is partially correct
8 Partially correct 90 ms 26172 KB Output is partially correct
9 Partially correct 68 ms 20112 KB Output is partially correct
10 Partially correct 101 ms 25292 KB Output is partially correct
11 Partially correct 104 ms 25044 KB Output is partially correct
12 Partially correct 56 ms 20844 KB Output is partially correct
13 Partially correct 64 ms 21992 KB Output is partially correct
14 Partially correct 67 ms 22024 KB Output is partially correct
15 Partially correct 69 ms 22088 KB Output is partially correct
16 Partially correct 8 ms 13036 KB Output is partially correct
17 Partially correct 52 ms 20616 KB Output is partially correct
18 Partially correct 61 ms 20596 KB Output is partially correct
19 Partially correct 58 ms 20560 KB Output is partially correct
20 Partially correct 82 ms 24660 KB Output is partially correct
21 Partially correct 81 ms 24696 KB Output is partially correct
22 Partially correct 79 ms 24380 KB Output is partially correct