Submission #155127

#	Time	Username	Problem	Language	Result	Execution time	Memory
155127		Mercenary	Xylophone (JOI18_xylophone)	C++14	100 / 100	130 ms	568 KiB

xylophone

#include<bits/stdc++.h>
#include "xylophone.h"
using namespace std;
const int maxn = 5005;
int a[maxn] , b[maxn];
int val[maxn];

void solve(int n) {
    for(int i = 1 ; i < n ; ++i){
        a[i] = query(i , i + 1);
    }
    for(int i = 1 ; i < n - 1 ; ++i){
        b[i] = query(i , i + 2);
    }
    int delta = 1;
    val[1] = 0;
    val[2] = a[1];
    for(int i = 3 ; i <= n ; ++i){
        if(a[i - 2] + a[i - 1] != b[i - 2]){
            delta = -delta;
        }
        val[i] = val[i - 1] + delta * a[i - 1];
    }
    pair<int,int> Min = make_pair(1e9 , 0);
    pair<int,int> Max = make_pair(-1e9 , 0);
    for(int i = 1 ; i <= n ; ++i){
        Min = min(Min , make_pair(val[i] , i));
        Max = max(Max , make_pair(val[i] , i));
    }
//    cout << n << endl;
    for(int i = 1 ; i <= n ; ++i){
        val[i] = val[i] - Min.first + 1;
        if(Min.second > Max.second)val[i] = n - val[i] + 1;
//        cout << i << " " << val[i] << endl;
        answer(i , val[i]);
    }
}

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