제출 #648084

#제출 시각아이디문제언어결과실행 시간메모리
648084Clan328동굴 (IOI13_cave)C++17
100 / 100
412 ms460 KiB
#include "cave.h" #include "bits/stdc++.h" using namespace std; typedef vector<int> vi; #define DOWN 1 #define UP 0 #define NA 2 int n; vi dir; int check(int tmp, int lo, int mid, int hi) { int arr[n]; for (int i = 0; i <= mid; i++) { if (dir[i] == NA) arr[i] = 1-tmp; else arr[i] = dir[i]; } for (int i = mid+1; i < n; i++) { if (dir[i] == NA) arr[i] = tmp; else arr[i] = dir[i]; } // for (int i = 0; i < n; i++) { // cout << (arr[i] == UP? "UP" : "DOWN") << " "; // } // cout << endl; return tryCombination(arr); } void exploreCave(int N) { int S[N]; int D[N]; dir = vi(N, NA); // Dir to open door n = N; for (int i = 0; i < N; i++) { D[i] = -1; } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { S[j] = DOWN; if (dir[j] != NA) S[j] = dir[j]; } // for (int j = 0; j < N; j++) { // if (D[j] != -1) S[D[j]] = dir[j]; // } // cout << S[2] << endl; // for (int j = 0; j < N; j++) { // cout << (S[j] == UP? "UP" : "DOWN") << " "; // } // cout << endl; int tmp = tryCombination(S); int tmpDir; if (tmp == i) { tmpDir = UP; } else tmpDir = DOWN; // cout << tmpDir << endl; int lo = 0, hi = N-1, mid; while (lo < hi) { mid = (lo+hi)/2; bool isDownI = check(tmpDir, lo, mid, hi) == i; // cout << lo << " " << mid << " " << isDownI << endl; if (isDownI) { hi = mid; } else lo = mid + 1; } D[lo] = i; if (tmp == i) { dir[lo] = UP; } else dir[lo] = DOWN; // cout << (dir[i] == UP? "UP" : "DOWN") << endl; // cout << "x: " << lo << endl; } for (int i = 0; i < N; i++) S[i] = dir[i]; // int res[N]; // for (int i = 0; i < N; i++) res[i] = dir[D[i]]; // for (int i = 0; i < N; i++) { // std::cout << S[i] << " "; // } // cout << endl; // for (int i = 0; i < N; i++) { // std::cout << D[i] << " "; // } // cout << endl; answer(S, D); }
#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...