Submission #823205

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
823205	2023-08-12T09:26:03 Z	Dremix10	Mechanical Doll (IOI18_doll)	C++17	16 / 100	72 ms	12492 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 <= 2){
            int idx = x.size() + 1;
            if(cnt == 1){
                x.push_back(-idx);
                y.push_back(nxt[i][0]);
            }
            else{
                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	0 ms	212 KB	Output is correct
2	Correct	37 ms	8376 KB	Output is correct
3	Correct	26 ms	7152 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	8 ms	3752 KB	Output is correct
6	Correct	39 ms	10956 KB	Output is correct
7	Correct	0 ms	300 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	37 ms	8376 KB	Output is correct
3	Correct	26 ms	7152 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	8 ms	3752 KB	Output is correct
6	Correct	39 ms	10956 KB	Output is correct
7	Correct	0 ms	300 KB	Output is correct
8	Correct	33 ms	8092 KB	Output is correct
9	Correct	42 ms	10808 KB	Output is correct
10	Correct	61 ms	12436 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	300 KB	Output is correct
13	Correct	1 ms	300 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	37 ms	8376 KB	Output is correct
3	Correct	26 ms	7152 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	8 ms	3752 KB	Output is correct
6	Correct	39 ms	10956 KB	Output is correct
7	Correct	0 ms	300 KB	Output is correct
8	Correct	33 ms	8092 KB	Output is correct
9	Correct	42 ms	10808 KB	Output is correct
10	Correct	61 ms	12436 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	300 KB	Output is correct
13	Correct	1 ms	300 KB	Output is correct
14	Correct	72 ms	12492 KB	Output is correct
15	Correct	34 ms	6692 KB	Output is correct
16	Correct	59 ms	10120 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	300 KB	Output is correct
20	Correct	64 ms	12340 KB	Output is correct
21	Correct	1 ms	296 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct