제출 #827380

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
827380		lukameladze	Mechanical Doll (IOI18_doll)	C++17	9 / 100	96 ms	36028 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
//#define int long long
#define pii pair <int, int>
#define ll long long
#define pb push_back
const int MX = 3e5 + 5;
int n, p[MX], cnt[MX], cur;
int resc[MX], resx[MX], resy[MX];
vector <int> v[MX];
vector < int > lst;
void go(int idx, int val) {
    if (val == 0) {
        lst.pb(idx); lst.pb(idx);
        // cout<<"add "<<idx<<"\n";
        return ;
    }
    // cout<<idx<<" --- > "<<cur - 1<<" "<<cur - 2<<"\n";
    resx[-idx] = --cur;
    resy[-idx] = --cur;
    lst.clear();
    vector <int> lst1, lst2;
    go(resx[-idx], val - 1);
    lst1 = lst;
    lst.clear();
    go(resy[-idx], val - 1);
    for (int i = 0; i < lst.size(); i++) lst2.pb(lst1[i]), lst2.pb(lst[i]);
    lst.clear();
    lst = lst2; 
    if (val == 0) return ;
}
void create_circuit(int M, vector<int> A) {
    n = A.size();
    for (int i = 0; i < n; i++) p[i] = A[i];
    p[n] = 0;
    for (int i = 0; i < n; i++) {
        cnt[p[i]]++;
        v[p[i]].pb(p[i + 1]);
    }
    resc[0] = p[0]; // resc.size() == M + 1
    vector <int> vis(MX, 0); 
    for (int i = 1; i <= n; i++) {
        if (!cnt[i]) continue;
        int bit = 0;
        lst.clear();
        for (int j = 0;; j++) if ((1<<j) >= cnt[i]) {bit = j; break;}
        if (bit == 0) {
            resc[i] = v[i][0]; continue;
        }
        resc[i] = --cur; int st = cur;
        // cout<<i<<"       "<<bit<<"\n";
        go(cur, bit - 1);
        int rem = (1<<bit) - cnt[i];
        assert((int)lst.size() == (1<<bit));
        // cout<<"order ";
        // for (int x : lst) cout<<x<<" ";
        // cout<<"\n";
        for (int i = 0; i < rem; i++) {
            // cout<<"trigg_back"<<-lst[i]<<" "<<-st<<"\n";
            vis[-lst[i]]++;
            if (vis[-lst[i]] % 2 == 1) resx[-lst[i]] = st;
            else resy[-lst[i]] = st;
        }
        for (int j = rem; j < (int)lst.size(); j++) {
            // cout<<"trig_front"<<-lst[j]<<" "<<v[i][j - rem]<<"\n";
            vis[-lst[j]]++;
            if (vis[-lst[j]] % 2 == 1) resx[-lst[j]] = v[i][j - rem];
            else resy[-lst[j]] = v[i][j - rem];
        }
    }
    vector <int> C(M + 1, 0);
    vector<int> X(-cur + 1, 0), Y(-cur + 1, 0);
    for (int i = 0; i < M + 1; i++) C[i] = resc[i];
    // for (int i = 0; i < M + 1; i++) cout<<C[i]<<" ";
    // cout<<"\n";
    for (int i = 0; i < -cur; i++) X[i] = resx[i + 1], Y[i] = resy[i + 1];//, cout<<resx[i + 1]<<" "<<resy[i + 1]<<"\n";
    // cout<<"\n";
    answer(C, X, Y);
}

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

doll.cpp: In function 'void go(int, int)':
doll.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 0; i < lst.size(); i++) lst2.pb(lst1[i]), lst2.pb(lst[i]);
      |                     ~~^~~~~~~~~~~~

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