Submission #1282414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282414		am_aadvik	Monster Game (JOI21_monster)	C++20	10 / 100	60 ms	424 KiB

monster

#define SUBMIT 1
#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include<iostream>
using namespace std;
#ifdef SUBMIT
	#include "monster.h"
#else

#include <cstdio>
#include <cstdlib>
namespace {
    using std::exit;
    using std::fprintf;
    using std::printf;
    using std::scanf;
    constexpr int Q_MAX = 25'000;
    constexpr int N_MAX = 1'000;
    int N;
    int S[N_MAX];
    int query_count = 0;
    void WrongAnswer(int code) {
        printf("Wrong Answer [%d]\n", code);
        exit(0);
    }
}
bool Query(int a, int b) {
    if (++query_count > Q_MAX) WrongAnswer(6);
    if (a < 0 || N <= a || b < 0 || N <= b) WrongAnswer(4);
    if (a == b) WrongAnswer(5);
    return (S[a] > S[b]) ^ (abs(S[a] - S[b]) == 1);
}
vector<int> Solve(int n);
int main() {
    if (scanf("%d", &N) != 1) {
        fprintf(stderr, "Error while reading.\n");
        exit(1);
    }
    for (int i = 0; i < N; i++) {
        if (scanf("%d", S + i) != 1) {
            fprintf(stderr, "Error while reading.\n");
            exit(1);
        }
    }
    std::vector<int> T = Solve(N);
    if ((int)T.size() != N) WrongAnswer(1);
    for (int i = 0; i < N; i++) {
        if (T[i] < 0 || N <= T[i]) WrongAnswer(2);
        if (T[i] != S[i]) WrongAnswer(3);
    }
    printf("Accepted: %d\n", query_count);
    return 0;
}
#endif

bool q(int a, int b) { return Query(a, b); }
vector<int> Solve(int n) {
    vector<int> win(n), a(n);
    for(int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j) {
            auto x = q(i, j);
            if (x) ++win[i];
            else ++win[j];
        }
    vector<int> w1, wn;
    for (int i = 0; i < n; ++i) {
        if (win[i] == 1) w1.push_back(i);
        else if (win[i] == (n - 2)) wn.push_back(i);
        else a[i] = win[i];
    }

    auto r1 = q(w1[0], w1[1]);
    if (r1) a[w1[0]] = 0, a[w1[1]] = 1;
    else a[w1[0]] = 1, a[w1[1]] = 0;
    auto rn = q(wn[0], wn[1]);
    if (rn) a[wn[0]] = n - 2, a[wn[1]] = n - 1;
    else a[wn[0]] = n - 1, a[wn[1]] = n - 2;
    return a;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75