Submission #565621

#	Time	Username	Problem	Language	Result	Execution time	Memory
565621		shrimb	Xylophone (JOI18_xylophone)	C++17	0 / 100	82 ms	196200 KiB

xylophone

#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")

#include "xylophone.h"
#include"bits/stdc++.h"
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;

// #define int long long
#define endl '\n'
#define mod 1000000007
//\
#define mod 1686876991

const int maxn = 5001;
int n;
int d[maxn];

int dp[maxn][maxn][2];
bool best[maxn][maxn][2];

bool rec (int i, int sm, bool seen) {
    if (sm > n || sm < 1 || (sm == n and !seen)) return 0;
    if (i == n - 1) return 1;
    if (dp[i][sm][seen] != -1) return dp[i][sm][seen];
    auto A = rec(i + 1, sm + d[i], seen || (sm + d[i] == n));
    auto B = rec(i + 1, sm - d[i], seen || (sm - d[i] == n));
    if (A) best[i][sm][seen] = 1;
    else best[i][sm][seen] = 0;
    return dp[i][sm][seen] = (A || B);
}

void follow (int i, int sm, bool seen) {
    cerr << sm << " ";
    answer(i + 1, sm);
    if (i >= n - 1) return;
    if (best[i][sm][seen]) follow(i + 1, sm + d[i], seen || (sm + d[i] == n));
    else follow(i + 1, sm - d[i], seen || (sm - d[i] == n));
}

void solve(int N) {
    n = N;
    memset(dp, -1, sizeof dp);
    for (int i = 2 ; i <= n ; i++) d[i-2] = query(i-1,i);
    for (int i = 1 ; i <= n ; i++) {
        if (rec(0, i, i==1)) {
            follow(0, i, i==1);
            return;
        }
    }
}

Compilation message (stderr)

xylophone.cpp:18:1: warning: multi-line comment [-Wcomment]
   18 | //\
      | ^
xylophone.cpp: In function 'bool rec(int, int, bool)':
xylophone.cpp:36:28: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   36 |     return dp[i][sm][seen] = (A || B);
      |            ~~~~~~~~~~~~~~~~^~~~~~~~~~

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