제출 #696819

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
696819		whqkrtk04	자동 인형 (IOI18_doll)	C++17	85.55 / 100	93 ms	12784 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 &s, 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 {
        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);
        //cout << X << Y << "\n";
        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, 0), X, Y;
    vector<vector<int>> nxt(C.size());
    A.push_back(0);
    for(int i = 1; i < A.size(); i++)
        nxt[A[i-1]].push_back(A[i]);
    C[0] = A[0];
    for(int i = 1, s = 0; i < C.size(); i++) {
        solve(s, C[i], X, Y, nxt[i]);
        //cout << s << "\n" << X << Y << "\n";
    }
    answer(C, X, Y);
}

컴파일 시 표준 에러 (stderr) 메시지

doll.cpp: In function 'void solve(int&, int&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
doll.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         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()) {
      |               ~~~~^~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:71:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i = 1; i < A.size(); i++)
      |                    ~~^~~~~~~~~~
doll.cpp:74:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i = 1, s = 0; i < C.size(); i++) {
      |                           ~~^~~~~~~~~~

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