Submission #823369

#	Time	Username	Problem	Language	Result	Execution time	Memory
823369		Dremix10	Mechanical Doll (IOI18_doll)	C++17	16 / 100	64 ms	11052 KiB

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 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56