# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
843726 | mickey080929 | Memory 2 (JOI16_memory2) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "Memory2_lib.h"
#include <bits/stdc++.h>
using namespace std;
int ret[110];
int cnt[110];
int chk[110];
vector<int> ans[110];
void Solve(int T, int N) {
int r = 2 * N;
while (true) {
if (r == 2) {
int x = -1, y = -1;
for (int i=0; i<2*N; i++) {
if (!chk[i]) {
if (x == -1) x = i;
else y = i;
}
}
ans[Flip(x, y)] = {x, y};
break;
}
int idx = rand() % r;
int pv;
for (int i=0; i<2*N; i++) {
if (!chk[i]) {
if (idx == 0) {
pv = i;
break;
}
idx --;
}
}
for (int i=0; i<N; i++) cnt[i] = 0;
for (int i=0; i<2*N; i++) {
if (pv == i || chk[i]) continue;
ret[i] = Flip(pv, i);
cnt[ret[i]] ++;
}
int cur = -1;
for (int i=0; i<N; i++) {
if (cnt[i] & 1) {
cur = i;
break;
}
}
for (int i=0; i<2*N; i++) {
if (pv == i || chk[i]) continue;
if (ret[i] != cur) {
ans[ret[i]].push_back(i);
chk[i] = 1;
r --;
}
}
}
for (int i=0; i<N; i++) {
Answer(ans[i][0], ans[i][1], i);
}
return;
}
#define MAX_N (50)
static int T;
static int N;
static int K;
static int P[MAX_N];
static int A[MAX_N * 2];
static int cnt_flip_called;
static int cnt_answer_called;
static void wrong_answer(int message){
printf("Wrong Answer[%d]\n", message);
exit(message);
}
static void correct_answer(){
printf("Accepted\n");
exit(0);
}
static int in_range(int lb, int ub, int x){
if(lb <= x && x < ub) return 1;
else return 0;
}
int Flip(int I, int J){
cnt_flip_called++;
if(cnt_flip_called > K){
wrong_answer(2);
}
if(I == J || in_range(0, N * 2, I) == 0 || in_range(0, N * 2, J) == 0){
wrong_answer(1);
}
if(P[A[I]] < P[A[J]]) return A[I];
else return A[J];
}
static int answered[MAX_N];
void Answer(int I, int J, int X){
if(in_range(0, N * 2, I) == 0 || in_range(0, N * 2, J) == 0 || I == J ||
A[I] != X || A[J] != X){
wrong_answer(3);
}
if(answered[X] != 0){
wrong_answer(4);
}
answered[X] = 1;
cnt_answer_called++;
}
int main(){
int i;
if(scanf("%d%d%d",&T, &N, &K) < 3){
fprintf(stderr, "error: cannot read T, N and K.\n");
exit(1);
}
if(N <= 0 || N > MAX_N){
fprintf(stderr, "error: N is out of bounds.\n");
exit(1);
}
for(i = 0; i < N; ++i){
if(scanf("%d", &(P[i])) < 1){
fprintf(stderr, "error: cannot read the sequence P.\n");
exit(1);
}
}
for(i = 0; i < N * 2; ++i){
if(scanf("%d", &(A[i])) < 1){
fprintf(stderr, "error: cannot read the sequence A.\n");
exit(1);
}
}
cnt_flip_called = 0;
cnt_answer_called = 0;
Solve(T, N);
if(cnt_answer_called != N){
wrong_answer(5);
}
correct_answer();
return 1;
}