Submission #491562

#	Time	Username	Problem	Language	Result	Execution time	Memory
491562		Alexandruabcde	Xylophone (JOI18_xylophone)	C++14	0 / 100	3 ms	288 KiB

xylophone

#include <bits/stdc++.h>
#include "xylophone.h"

using namespace std;

constexpr int NMAX = 5005;

int D[NMAX];
int T[NMAX];

int val[NMAX];
bool fr[NMAX];

int modul (int x) {
    if (x < 0) return -x;

    return x;
}

int FindThird (int a, int b, int ans_1, int ans_2, int ans_3) {
    int c = -1;
    if (ans_3 == ans_1) {
        if (b < a) c = b + ans_2;
        else c = b - ans_2;
    }
    else {
        c = b - ans_2;

        if (max(c, max(a, b)) - min(c, min(a, b)) == ans_3 && c > 0) return c;
        else c = b + ans_2;
    }

    return c;
}

void solve(int N) {
    for (int i = 1; i < N; ++ i )
        D[i] = query(i, i+1);
    for (int i = 1; i < N-1; ++ i )
        T[i] = query(i, i+2);

    for (int i = 1; i <= N; ++ i ) {
        val[i] = N;
        for (int j = 1; j <= N; ++ j )
            fr[j] = 0;

        fr[val[i]]++;
        bool ok = 1;

        if (i != N)
            val[i+1] = val[i] - D[i];
        if (i != 1)
            val[i-1] = val[i] - D[i-1];

        fr[val[i-1]]++;
        fr[val[i+1]]++;

        if (fr[val[i-1]] > 1 || fr[val[i+1]] > 1) continue;

        for (int j = i + 2; j <= N; ++ j ) {
            val[j] = FindThird(val[j-2], val[j-1], D[j-2], D[j-1], T[j-2]);

            if (val[j] < 1 || val[j] > N || fr[val[j]] > 0) {
                ok = false;
                break;
            }
            fr[val[j]]++;
        }

        for (int j = i-2; j >= 1; -- j ) {
            val[j] = FindThird(val[j+2], val[j+1], D[j+1], D[j], T[j]);

            if (val[j] < 1 || val[j] > N || fr[val[j]] > 0) {
                ok = false;
                break;
            }
            fr[val[j]]++;
        }

        if (ok) {
            int poz_1 = 0, poz_N = i;
            for (int j = 1; j <= N; ++ j )
                if (val[j] == 1) poz_1 = j;

            if (poz_1 > poz_N) continue;

            for (int j = 1; j <= N; ++ j )
                answer(j, val[j]);
            break;
        }
    }
}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:47:18: warning: use of an operand of type 'bool' in 'operator++' is deprecated [-Wdeprecated]
   47 |         fr[val[i]]++;
      |         ~~~~~~~~~^
xylophone.cpp:55:20: warning: use of an operand of type 'bool' in 'operator++' is deprecated [-Wdeprecated]
   55 |         fr[val[i-1]]++;
      |         ~~~~~~~~~~~^
xylophone.cpp:56:20: warning: use of an operand of type 'bool' in 'operator++' is deprecated [-Wdeprecated]
   56 |         fr[val[i+1]]++;
      |         ~~~~~~~~~~~^
xylophone.cpp:58:26: warning: comparison of constant '1' with boolean expression is always false [-Wbool-compare]
   58 |         if (fr[val[i-1]] > 1 || fr[val[i+1]] > 1) continue;
      |             ~~~~~~~~~~~~~^~~
xylophone.cpp:58:46: warning: comparison of constant '1' with boolean expression is always false [-Wbool-compare]
   58 |         if (fr[val[i-1]] > 1 || fr[val[i+1]] > 1) continue;
      |                                 ~~~~~~~~~~~~~^~~
xylophone.cpp:67:22: warning: use of an operand of type 'bool' in 'operator++' is deprecated [-Wdeprecated]
   67 |             fr[val[j]]++;
      |             ~~~~~~~~~^
xylophone.cpp:77:22: warning: use of an operand of type 'bool' in 'operator++' is deprecated [-Wdeprecated]
   77 |             fr[val[j]]++;
      |             ~~~~~~~~~^

• Subtask 1: 0 / 11
• Subtask 2: 0 / 36
• Subtask 3: 0 / 53