제출 #82344

#제출 시각아이디문제언어결과실행 시간메모리
82344PowerOfNinjaGo자동 인형 (IOI18_doll)C++17
70.67 / 100
265 ms14816 KiB
#include "doll.h" #include <bits/stdc++.h> using namespace std; #define X first #define Y second #define pb push_back typedef pair<int, int> ii; typedef long long ll; int high; const int maxn = 8e5+5; int L[maxn], R[maxn]; vector<int> all, matter; void build(int cur, int bit, int dep, int to) { // printf("%d ", cur); if(dep == high) { if(bit&1) R[cur] = -to; else L[cur] = -to; return; } if(bit&(1<<(high-dep))) { R[cur] = cur*2+1; build(cur*2+1, bit, dep+1, to); } else { L[cur] = cur*2; build(cur*2, bit, dep+1, to); } } bool cmp(int a, int b) { for(int i = 0; i<= high; i++) { int x = a & (1<<i); int y = b & (1<<i); if(x != y) return x< y; } } void create_circuit(int m, vector<int> A) { memset(L, 31, sizeof L); memset(R, 31, sizeof R); int n = A.size(); int leaves = n; int sig = -1; for(int i = 20; i>= 0; i--) { if((1<<i) & leaves) { sig = i+1; break; } } high = sig; for(int i = 0; i< n; i++) all.pb(i); all.pb((1<<high)-1); sort(all.begin(), all.end(), cmp); // printf("%d\n", high); for(int i = 0; i<= n; i++) { // printf("insert %d\n", all[i]); build(1, all[i], 1, i< n?A[i]:0); // printf("\n"); } for(int i = 1; i< (1<<high); i++) { if(L[i]> 0 && L[i] != 522133279) matter.pb(L[i]); if(R[i]> 0 && R[i] != 522133279) matter.pb(R[i]); } matter.pb(1); sort(matter.begin(), matter.end()); // printf("%d\n", matter.size()); vector<int> ansx, ansy; ansx.resize(matter.size()); ansy.resize(matter.size()); vector<int> res(m+1, -1); for(int i = 0; i< (int) matter.size(); i++) { int sw = matter[i]; // printf("%d: %d %d\n", sw, L[sw], R[sw]); if(L[sw]> 0) { if(L[sw] == 522133279) ansx[i] = -1; else ansx[i] = -(lower_bound(matter.begin(), matter.end(), L[sw])-matter.begin()+1); } else { ansx[i] = -L[sw]; } if(R[sw]> 0) { if(R[sw] == 522133279) ansy[i] = -1; else ansy[i] = -(lower_bound(matter.begin(), matter.end(), R[sw])-matter.begin()+1); } else { ansy[i] = -R[sw]; } // printf("res %d %d\n", ansx[i], ansy[i]); } answer(res, ansx, ansy); }

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

doll.cpp: In function 'bool cmp(int, int)':
doll.cpp:46:1: warning: control reaches end of non-void function [-Wreturn-type]
   46 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...