제출 #815477

#제출 시각아이디문제언어결과실행 시간메모리
815477Sohsoh84Memory 2 (JOI16_memory2)C++17
60 / 100
1 ms468 KiB
#include "Memory2_lib.h" #include <bits/stdc++.h> using namespace std; const int MAXN = 1e3 + 10; #define sep ' ' #define debug(x) cerr << #x << ": " << x << endl; vector<int> rem_inds; bool flag[MAXN], asked[MAXN][MAXN]; vector<int> vec[MAXN]; int FFF[MAXN][MAXN], N; inline void add(int ind, int val) { vec[val].push_back(ind); flag[ind] = true; rem_inds.erase(find(rem_inds.begin(), rem_inds.end(), ind)); } inline int ask(int i, int j) { if (i > j) swap(i, j); if (!asked[i][j]) { asked[i][j] = true; FFF[i][j] = Flip(i, j); } return FFF[i][j]; } inline void answer() { for (int i = 0; i < N; i++) { while (int(vec[i].size()) < 2) { vec[i].push_back(rem_inds.back()); rem_inds.pop_back(); } Answer(vec[i][0], vec[i][1], i); } } void Solve(int T, int N_) { N = N_; if (N == 1) { Answer(0, 1, 0); return; } for (int i = 0; i < 2 * N; i++) rem_inds.push_back(i); while (int(rem_inds.size()) >= 4) { vector<int> f; for (int i = 0; i < 4; i++) f.push_back(rem_inds[i]); vector<int> ans = {-1}; for (int j = 1; j < 4; j++) ans.push_back(ask(f[0], f[j])); if (ans[1] == ans[2] && ans[2] == ans[3]) { add(f[0], ans[1]); } else { auto ind = min_element(ans.begin() + 1, ans.end()) - ans.begin(); add(f[ind], ans[ind]); } } vector<int> V1, V2; for (int i = 0; i < N; i++) { if (int(vec[i].size()) == 1) V1.push_back(i); else if (int(vec[i].size()) == 0) V2.push_back(i); } if (int(V1.size()) == 3) { sort(rem_inds.begin(), rem_inds.end()); do { bool flag = true; for (int i = 0; i < 3; i++) flag &= (ask(vec[V1[i]].front(), rem_inds[i]) == i); if (flag) { for (int i = 0; i < 3; i++) vec[V1[i]].push_back(rem_inds[i]); answer(); return; } } while (next_permutation(rem_inds.begin(), rem_inds.end())); } vector<int> ans; for (int i = 0; i < 3; i++) ans.push_back(ask(vec[V1[0]].front(), rem_inds[i])); if (ans[0] != ans[1] || ans[1] != ans[2]) { int val = *max_element(ans.begin(), ans.end()); for (int i = 0; i < 3; i++) { if (ask(vec[V1[0]].front(), rem_inds[i]) == val) { add(rem_inds[i], V1[0]); break; } } answer(); return; } for (int i = 0; i < 3; i++) { if (ask(rem_inds[i], rem_inds[(i + 1) % 3]) == ask(rem_inds[i], rem_inds[(i + 2) % 3])) { add(rem_inds[i], V1[0]); break; } } answer(); return; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...