Submission #108455

#	Time	Username	Problem	Language	Result	Execution time	Memory
108455		someone_aa	Xylophone (JOI18_xylophone)	C++17	0 / 100	70 ms	98552 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
//static int A[5000];
int answ[5010][5010];
int temp[5010];
int cnt[5010];

int aask(int i, int j) {
    if(answ[i][j] == -1) return answ[i][j] = query(i+1, j+1);
    else return answ[i][j];
}

void solve(int N) {
    memset(answ,-1,sizeof(answ));
    for(int i=0;i<N;i++) {
        memset(temp,0,sizeof(temp));
        temp[i] = 0;
        if(i<N-1) {
            int c = aask(i, i+1);
            temp[i+1] = c;

            for(int j=i+2;j<N;j++) {
                int a1 = aask(j-1, j);
                int a2 = aask(j-2, j);
                int a3 = aask(j-2, j-1);
                if(a2 == a3) {
                    if(temp[j-1] > temp[j-2]) temp[j] = temp[j-1] - a1;
                    else if(temp[j-1] < temp[j-2]) temp[j] = temp[j-1] + a1;
                }
                else if(a2 == a1) {
                    if(temp[j-1] < temp[j-2]) temp[j] = temp[j-1] + a1;
                    else if(temp[j-1] > temp[j-2]) temp[j] = temp[j-1] - a1;
                }
                else {
                    if(temp[j-1] > temp[j-2]) temp[j] = temp[j-1] + a1;
                    else if(temp[j-1] < temp[j-2]) temp[j] = temp[j-1] - a1;
                }
            }
        }

        if(i>=1) {
            int c = aask(i-1, i);
            temp[i-1] = c;
            for(int j=i-2;j>=0;j--) {
                int a1 = aask(j, j+1);
                int a2 = aask(j+1, j+2);
                int a3 = aask(j, j+2);

                if(a3 == a2) {
                    // temp[j] is M
                    if(temp[j+1] > temp[j+2]) temp[j] = temp[j+1] - a1;
                    else if(temp[j+1] < temp[j+2]) temp[j] = temp[j+1] + a1;
                }
                else if(a3 == a1) {
                    // temp[j] is L or S
                    if(temp[j+1] > temp[j+2]) temp[j] = temp[j+1] - a1;
                    else if(temp[j+1] < temp[j+2]) temp[j] = temp[j+1] + a1;
                }
                else {
                    if(temp[j+1] > temp[j+2]) temp[j] = temp[j+1] + a1;
                    else if(temp[j+1] < temp[j+2]) temp[j] = temp[j+1] - a1;
                }
            }
        }
        bool valid = true;
        for(int j=0;j<N;j++) {
            if(temp[j] < 0 || temp[j] > N) valid = false;
        }
        memset(cnt,0,sizeof(cnt));

        if(valid) {
            for(int j=0;j<N;j++) {
                cnt[temp[j]]++;
            }
            for(int j=0;j<N;j++) {
                if(cnt[j] != 1) valid = false;
            }
        }

        if(valid) {
            for(int j=0;j<N;j++) {
                answer(j+1, temp[j]);
            }
            break;
        }
    }
}

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