제출 #687358

#제출 시각아이디문제언어결과실행 시간메모리
687358Bliznetc동굴 (IOI13_cave)C++17
51 / 100
202 ms428 KiB
#include "cave.h" #include <bits/stdc++.h> #include <stdlib.h> #include <stdio.h> using namespace std; #define pb push_back #define sz size() #define all(x) x.begin(), x.end() #define F first #define S second #define MAX_N 5000 #define MAX_CALLS 70000 typedef pair < int, int > pii; typedef vector < int > vi; typedef vector < vi > vvi; /*int N; static int realS[MAX_N]; static int realD[MAX_N]; static int inv[MAX_N]; static int num_calls; void answer(int S[], int D[]) { int i; int correct = 1; for (i = 0; i < N; ++i) if (S[i] != realS[i] || D[i] != realD[i]) { correct = 0; break; } if (correct) printf("CORRECT\n"); else printf("INCORRECT\n"); for (i = 0; i < N; ++i) { if (i > 0) printf(" "); printf("%d", S[i]); } printf("\n"); for (i = 0; i < N; ++i) { if (i > 0) printf(" "); printf("%d", D[i]); } printf("\n"); exit(0); } int tryCombination(int S[]) { int i; // for (i = 0; i < N; i++) { // cout << S[i] << " "; // } // cout << "\n"; if (num_calls >= MAX_CALLS) { printf("INCORRECT\nToo many calls to tryCombination().\n"); exit(0); } ++num_calls; for (i = 0; i < N; ++i) if (S[inv[i]] != realS[inv[i]]) return i; return -1; } int init() { int i, res; FILE *f = fopen("cave.in", "r"); if (!f) fail("Failed to open input file."); res = fscanf(f, "%d", &N); for (i = 0; i < N; ++i) { res = fscanf(f, "%d", &realS[i]); } for (i = 0; i < N; ++i) { res = fscanf(f, "%d", &realD[i]); inv[realD[i]] = i; } num_calls = 0; return N; }*/ void exploreCave (int n) { int ask[n]; int good[n]; int d[n]; for (int i = 0; i < n; i++) { good[i] = d[i] = -1; } // vector<int> good(n, -1), d(n, -1); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (good[j] == -1) { ask[j] = 0; } else { ask[j] = good[j]; } } int x = tryCombination(ask); if (x == i) { for (int j = 0; j < n; j++) { if (good[j] == -1) { ask[j] = 1; } else { ask[j] = good[j]; } } } int l = 0, r = n - 1; while (r - l > 0) { int mid = (l + r) / 2; for (int j = l; j <= mid; j++) { if (good[j] == -1) { ask[j] = 1 - ask[j]; } else { ask[j] = good[j]; } } x = tryCombination(ask); // cout << i << " - " << x << " " << l << " " << r << "\n"; if (x == i) { for (int j = l; j <= mid; j++) { if (good[j] == -1) { ask[j] = 1 - ask[j]; } else { ask[j] = good[j]; } } for (int j = mid + 1; j <= r; j++) { if (good[j] == -1) { ask[j] = 1 - ask[j]; } else { ask[j] = good[j]; } } r = mid; } else { l = mid + 1; } // cout << l << " " << r << ":\n"; // for (int j = 0; j < n; j++) { // cout << ask[j] << " "; // } // cout << "\n"; } if (good[l] == -1) { ask[l] = 1 - ask[l]; } else { ask[l] = good[l]; } x = tryCombination(ask); if (x == i) { if (good[l] == -1) { ask[l] = 1 - ask[l]; } else { ask[l] = good[l]; } l = r; } good[l] = ask[l]; d[l] = i; // cout << i << " - " << l << " " << good[i] << " " << d[l] << "\n"; // cout << "\n"; } answer(good, d); } /* int main() { int N; N = init(); exploreCave(N); printf("INCORRECT\nYour solution did not call answer().\n"); return 0; }*/ /* signed main() { vi a; a.pb(-2); a.pb(2); a.pb(2); a.pb(-2); a.pb(-2); a.pb(2); cout << count_swaps(a); } */
#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...