Submission #696829

#	Time	Username	Problem	Language	Result	Execution time	Memory
696829		whqkrtk04	Mechanical Doll (IOI18_doll)	C++17	100 / 100	109 ms	7948 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000007;
const ll LLINF = (ll)1e18+1;
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }

void make(int &s, int cnt, int root, int idx, int lvl, vector<int> &X, vector<int> &Y) {
    if(lvl == 2) {
        if(cnt == 1) X[idx] = root;
        else X[idx] = INF;
        Y[idx] = INF;
    } else {
        if(cnt > lvl/2) {
            X[idx] = -(++s);
            X.push_back(0); Y.push_back(0);
            make(s, cnt-lvl/2, root, -X[idx]-1, lvl/2, X, Y);
            Y[idx] = -(++s);
            X.push_back(0); Y.push_back(0);
            make(s, lvl/2, root, -Y[idx]-1, lvl/2, X, Y);
        } else {
            X[idx] = root;
            Y[idx] = -(++s);
            X.push_back(0); Y.push_back(0);
            make(s, cnt, root, -Y[idx]-1, lvl/2, X, Y);
        }
    }
}

void solve(int &c, vector<int> &X, vector<int> &Y, vector<int> &nxt) {
    if(nxt.size() == 0) {
        c = 0;
    } else if(nxt.size() == 1) {
        c = nxt[0];
    } else {
        int s = 0;
        c = -(++s);
        X.push_back(0); Y.push_back(0);
        int lvl = 1;
        while(lvl < nxt.size()) lvl <<= 1;
        make(s, nxt.size(), c, -c-1, lvl, X, Y);
        int here = c, cnt = 0;
        vector<bool> chk(s+c+1, true);
        while(cnt < nxt.size()) {
            //cout << here << " " << c << "\n";
            int& there = (chk[-here+c] ? X[-here-1] : Y[-here-1]);
            chk[-here+c] = !chk[-here+c];
            if(there == INF) {
                there = nxt[cnt++];
                here = c;
            } else here = there;
        }
    }
}

void create_circuit(int M, vector<int> A) {
    vector<int> C(M+1, -1), X, Y;
    A.push_back(0);
    solve(C[0], X, Y, A);
    answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void solve(int&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
doll.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         while(lvl < nxt.size()) lvl <<= 1;
      |               ~~~~^~~~~~~~~~~~
doll.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         while(cnt < nxt.size()) {
      |               ~~~~^~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56