Submission #823369

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
823369	2023-08-12T12:01:58 Z	Dremix10	Mechanical Doll (IOI18_doll)	C++17	16 / 100	64 ms	11052 KB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
const int N = 3e5+5;
const ll INF = 1e18+5;
const int MOD = 1e9+7;


void create_circuit(int m, vector<int> arr) {
    int n = arr.size();

    vector<int> x,y,c(m+1);

    /// origin goes to first trigger
    c[0] = arr[0];

    int i;
    vector<vector<int> > nxt(m+1);

    for(i=0;i<n;i++){
        if(i < n-1)
            nxt[arr[i]].push_back(arr[i+1]);
        else
            nxt[arr[i]].push_back(0);
    }

    for(i=1;i<=m;i++){
        int cnt = nxt[i].size();
        if(cnt == 0)continue;
        else if(cnt == 1){
            c[i] = nxt[i][0];
        }
        else if(cnt == 2){
            int idx = x.size() + 1;

            x.push_back(nxt[i][0]);
            y.push_back(nxt[i][1]);
        
            c[i] = -idx;
        }
        else{
            int idx = x.size() + 1;
            c[i] = -idx;
            
            // create 2 children
            idx++;
            x.push_back(-idx);

            idx++;
            y.push_back(-idx);

            // child 1
            x.push_back(nxt[i][0]);
            if(cnt==3){
                y.push_back(-(idx-2));
            }
            else{
                y.push_back(nxt[i][2]);
            }

            // child 2
            x.push_back(nxt[i][1]);
            // goes to last one always
            y.push_back(nxt[i].back());


        }

    }

    answer(c,x,y);

}

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	19 ms	6356 KB	Output is correct
3	Correct	16 ms	5200 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	8 ms	3796 KB	Output is correct
6	Correct	25 ms	7740 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	19 ms	6356 KB	Output is correct
3	Correct	16 ms	5200 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	8 ms	3796 KB	Output is correct
6	Correct	25 ms	7740 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	37 ms	7248 KB	Output is correct
9	Correct	36 ms	8576 KB	Output is correct
10	Correct	56 ms	11052 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	19 ms	6356 KB	Output is correct
3	Correct	16 ms	5200 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	8 ms	3796 KB	Output is correct
6	Correct	25 ms	7740 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	37 ms	7248 KB	Output is correct
9	Correct	36 ms	8576 KB	Output is correct
10	Correct	56 ms	11052 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	62 ms	10932 KB	Output is correct
15	Correct	33 ms	5832 KB	Output is correct
16	Correct	62 ms	8632 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	64 ms	10676 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct