Submission #836127

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
836127	2023-08-24T07:45:52 Z	mousebeaver	Mechanical Doll (IOI18_doll)	C++14	16 / 100	70 ms	11056 KB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

void dfs(vector<int> adjlist, vector<int>& x, vector<int>& y)
{
    //adjlist.size() > 1, insert new switch
    if(adjlist.size()%2 == 0)
    {
        x.push_back(0);
        y.push_back(0);
        int index = x.size()-1;    
        if(adjlist.size() == 2)
        {
            x.back() = adjlist[0];
            y.back() = adjlist[1];
            return;
        }
        vector<int> even(0);
        vector<int> odd(0);
        for(int i = 0; i < (int) adjlist.size(); i++)
        {
            if(i%2 == 0)
            {
                even.push_back(adjlist[i]);
            }
            else
            {
                odd.push_back(adjlist[i]);
            }
        }
        
        x[index] = -(x.size()+1);
        dfs(even, x, y);

        y[index] = -(x.size()+1);
        dfs(odd, x, y);
        return;
    }

    //Uneven size of adjlist?
    int index = x.size();
    x.push_back(0);
    y.push_back(0);
    x.back() = -(x.size()+1);
    y.back() = -(x.size()+2);
    x.push_back(adjlist[0]);
    y.push_back(adjlist[1]);
    x.push_back(-(index+1));
    y.push_back(adjlist[2]);
}

void create_circuit(int m, std::vector<int> a) 
{
    int n = a.size();
    vector<vector<int>> adjlist(m+1, vector<int> (0));
    adjlist[0] = {a[0]};
    for(int i = 0; i < n-1; i++)
    {
        adjlist[a[i]].push_back(a[i+1]);
    }
    adjlist[a[n-1]].push_back(0);

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

    for(int i = 0; i <= m; i++)
    {
        if(adjlist[i].empty())
        {
            continue;
        }
        if(adjlist[i].size() == 1)
        {
            c[i] = adjlist[i][0];
            continue;
        }
        c[i] = -(x.size()+1);
        dfs(adjlist[i], x, y);
    }

    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	19 ms	6356 KB	Output is correct
3	Correct	16 ms	5076 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	11 ms	3840 KB	Output is correct
6	Correct	24 ms	7636 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	0 ms	212 KB	Output is correct
2	Correct	19 ms	6356 KB	Output is correct
3	Correct	16 ms	5076 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	11 ms	3840 KB	Output is correct
6	Correct	24 ms	7636 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	33 ms	7248 KB	Output is correct
9	Correct	35 ms	8656 KB	Output is correct
10	Correct	53 ms	11056 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	0 ms	212 KB	Output is correct
2	Correct	19 ms	6356 KB	Output is correct
3	Correct	16 ms	5076 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	11 ms	3840 KB	Output is correct
6	Correct	24 ms	7636 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	33 ms	7248 KB	Output is correct
9	Correct	35 ms	8656 KB	Output is correct
10	Correct	53 ms	11056 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	70 ms	10944 KB	Output is correct
15	Correct	43 ms	5984 KB	Output is correct
16	Correct	58 ms	8888 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	59 ms	10868 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct