제출 #776039

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
776039		Magikarp4000	자동 인형 (IOI18_doll)	C++17	53 / 100	113 ms	25896 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int MAXN = 4e5+5;
int n,m;
vector<int> c,x,y,nxt[MAXN];
bool z[MAXN], t[MAXN];

void create_circuit(int M, vector<int> a) {
    n = a.size(), m = M;
    FOR(_,0,m+1) c.PB(0);
    c[0] = a[0];
    a.PB(0);
    FOR(i,0,n) {
        nxt[a[i]].PB(a[i+1]);
    }
    int cur = -1;
    FOR(i,0,n) {
        if (z[a[i]]) continue;
        z[a[i]] = 1;
        int cnt = nxt[a[i]].size(), start = cur;
        if (cnt == 1) {
            c[a[i]] = nxt[a[i]][0];
            continue;
        }
        c[a[i]] = cur;
        cur--;
        int tgt = x.size()+cnt-1;
        int num = 2;
        int lg = ceil(log2(cnt));
        int cnt1 = 1<<lg;
        int thrsh = 2*cnt-cnt1;
        while (num < cnt1) {
            x.PB(cur--);
            num++;
            y.PB(cur--);
            num++;
        }
        int xsz = x.size(), ysz = y.size();
        FOR(_,0,thrsh/2) {
            x.PB(-INF);
            y.PB(-INF);
        }
        FOR(_,0,cnt-thrsh) {
            x.PB(start);
            y.PB(-INF);
        }
        int ball = start, idx = 0;
        while (idx < cnt) {
            int real = -ball-1;
            ball = t[real] ? y[real] : x[real];
            if (ball == -INF) {
                if (t[real] == 0) x[real] = nxt[a[i]][idx];
                else y[real] = nxt[a[i]][idx];
                idx++;
                ball = start;
            }
            t[real] ^= 1;
        }
    }
    // FORX(u,c) cout << u << " ";
    // cout << ln;
    // FORX(u,x) cout << u << " ";
    // cout << ln;
    // FORX(u,y) cout << u << " ";
    // cout << ln;
    answer(c,x,y);
}

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

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:50:13: warning: unused variable 'tgt' [-Wunused-variable]
   50 |         int tgt = x.size()+cnt-1;
      |             ^~~
doll.cpp:61:13: warning: unused variable 'xsz' [-Wunused-variable]
   61 |         int xsz = x.size(), ysz = y.size();
      |             ^~~
doll.cpp:61:29: warning: unused variable 'ysz' [-Wunused-variable]
   61 |         int xsz = x.size(), ysz = y.size();
      |                             ^~~

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