제출 #1109474

#제출 시각아이디문제언어결과실행 시간메모리
1109474SonicML동굴 (IOI13_cave)C++14
100 / 100
356 ms812 KiB
#include <iostream> #include "cave.h" int n; int const NMAX = 5000; int query[1 + NMAX]; bool fixed[1 + NMAX]; int sol[2][1 + NMAX]; void printQuery() { for(int i = 0;i < n;i++) { std::cerr << query[i] << ' '; } std::cerr << '\n'; } void buildQuery(int val1, int val2, int mid) { int ind = 0; for(int i = 0;i < n;i++) { if(!fixed[i]) { ind++; if(ind <= mid) { query[i] = val1; }else { query[i] = val2; } } } } int getPos(int mid) { int ind = 0; for(int i = 0;i < n;i++) { if(!fixed[i]) { ind++; if(ind == mid) { return i; } } } return -1; } int cautbin(int from, int to, int val1, int val2, int target) { //std::cerr << from << ' ' << to << " :\n"; if(from >= to) { return from; }else { int mid = (from + to) / 2; buildQuery(val1, val2, mid); int temp = tryCombination(query); //printQuery(); //std::cerr << " " << target << ' ' << mid << ' ' << temp << '\n'; if(temp == -1 || temp > target) { return cautbin(from, mid, val1, val2, target); }else { return cautbin(mid+1, to, val1, val2, target); } } } void solve() { for(int i = 0;i < n;i++) { int temp, val1 = 1, val2 = 0; buildQuery(0, 0, 0); //printQuery(); temp = tryCombination(query); //std::cerr << temp << '\n'; if(temp == -1 || temp > i) { val1 = 0; val2 = 1; } //std::cerr << i << ":\n"; int pos = getPos(cautbin(1, n-i, val1, val2, i)); //std::cerr << pos << "\n\n"; query[pos] = val1; fixed[pos] = true; sol[0][pos] = val1; sol[1][pos] = i; } } void exploreCave(int N) { n = N; solve(); answer(sol[0], sol[1]); }
#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...