Submission #525214

#	Time	Username	Problem	Language	Result	Execution time	Memory
525214		AA_Surely	Xylophone (JOI18_xylophone)	C++17	100 / 100	416 ms	20984 KiB

xylophone

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

#define FOR(i,x,n) for(int i = x; i < n; i++)
#define F0R(i,n) FOR(i, 0, n)
#define ROF(i,x,n) for(int i = n - 1; i >= x; i--)
#define R0F(i,n) ROF(i, 0, n)

#define pb push_back

using namespace std;

const int MAXN = 5000 + 7;
int keep[MAXN][MAXN], ans[MAXN];
int fake_ans[MAXN], cnt[MAXN];

void haveLfindR(int x) {
    //x is the place of first -> with arr[x] = p1, arr[x + 1] = p2 we have to find arr[x + 2] = ?

    if (fake_ans[x] > fake_ans[x + 1]) {
        if (abs(-keep[x][x + 1] - keep[x + 1][x + 2]) == keep[x][x + 2]) {
            //cout << "HERE FOR FINDING: " << x + 3 << endl;
            fake_ans[x + 2] = fake_ans[x + 1] - keep[x + 1][x + 2];
        }
        
        else {
            //cout << "GOOD" << endl;
            fake_ans[x + 2] = fake_ans[x + 1] + keep[x + 1][x + 2];
        }
    }

    else {
        if (keep[x][x + 1] + keep[x + 1][x + 2] == keep[x][x + 2]) {
            //cout << "SHIT FOR: " << x + 3 << endl;
            fake_ans[x + 2] = fake_ans[x + 1] + keep[x + 1][x + 2];
        }

        else {
            //cout << "WTF BRO: " << x + 3 << endl;
            fake_ans[x + 2] = fake_ans[x + 1] - keep[x + 1][x + 2];
        }
    }
    
    return;
}

void haveRfindL(int x) {
    if (fake_ans[x + 2] > fake_ans[x + 1]) {
        if (abs(-keep[x + 2][x + 1] - keep[x + 1][x]) == keep[x + 2][x]) 
            fake_ans[x] = fake_ans[x + 1] - keep[x + 1][x];
        
        else
            fake_ans[x] = fake_ans[x + 1] + keep[x + 1][x];
    }

    else {
        if (keep[x + 2][x + 1] + keep[x + 1][x] == keep[x + 2][x])
            fake_ans[x] = fake_ans[x + 1] + keep[x + 1][x];

        else
            fake_ans[x] = fake_ans[x + 1] - keep[x + 1][x];
    }
    
    return;
}

inline bool check(int n) {
    fill(cnt, cnt + n, 0);
    F0R(i, n) if(fake_ans[i] <= 0 || fake_ans[i] > n) return 0;
    F0R(i, n) cnt[fake_ans[i]]++;
    FOR(i, 1, n + 1) if (cnt[i] > 1 || !cnt[i]) return 0;

    return 1;
}

void solve(int n) {
    F0R(i, n - 1) 
        keep[i][i + 1] = keep[i + 1][i] = query(i + 1, i + 2);

    F0R(i, n - 2)
        keep[i][i + 2] = keep[i + 2][i] = query(i + 1, i + 3);
    
    /*
    FOR(i, 1, 3) {
        F0R(j, n) cout << keep[j][j + i] << ' ';
        cout << endl;
    }
    */

    //cout << endl;
    F0R(i, n) {
        //guessing this is the minimum
        fake_ans[i] = 1;
        if (i > 0) fake_ans[i - 1] = 1 + keep[i][i - 1];
        if (i < n - 1) fake_ans[i + 1] = 1 + keep[i][i + 1];

        FOR(j, i, n - 2) haveLfindR(j);
        R0F(j, i - 1) haveRfindL(j);
        
        /*
        F0R(j, n) cout << fake_ans[j] << ' ';
        cout << endl;
        */
        

        if (check(n)) {
            F0R(j, n) ans[j] = fake_ans[j];
            break;
        }
    }

    F0R(i, n) answer(i + 1, ans[i]);
    return;
}

/*
int main() {
    int n; cin >> n;
    solve(n);
}
*/

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