Submission #99565

#	Time	Username	Problem	Language	Result	Execution time	Memory
99565		oolimry	Xylophone (JOI18_xylophone)	C++14	100 / 100	92 ms	544 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
void solve(int N) {
    int n = N;
	int two[n];
	int three[n];
	for(int i = 1;i < n;i++){
        two[i] = query(i,i+1);
	}
	for(int i = 2;i < n;i++){
        three[i] = query(i-1,i+1);
	}

	int arr[n];
	arr[0] = 0;
	arr[1] = two[1];
    typedef pair<int,int> ii;

    for(int i = 2;i < n;i++){
        ///in between previous two
        ///i-1,i,i-2 or i-2,i,i-1
        if(three[i] == two[i-1]){
            if(arr[i-1] > arr[i-2]){
                arr[i] = arr[i-1] - two[i];
            }
            else{
                arr[i] = arr[i-1] + two[i];
            }
        }
        else{
            ///i-2 is the middle element
            ///i,i-2,i-1 or i-1,i-2,1
            if(three[i] == two[i]){
                if(arr[i-1] > arr[i-2]){
                    arr[i] = arr[i-1] - two[i];
                }
                else{
                    arr[i] = arr[i-1] + two[i];
                }
            }
            ///i-1 is the middle element
            ///i,i-1,i-2 or i-2,i-1,i
            else{
                if(arr[i-1] > arr[i-2]){
                    arr[i] = arr[i-1] + two[i];
                }
                else{
                    arr[i] = arr[i-1] - two[i];
                }
            }
        }
    }

    ii v[n];
    for(int i = 0;i < n;i++){
        v[i] = ii(arr[i],i+1);
    }
    sort(v,v+n);
    if(v[0].second > v[n-1].second){
        for(int i = 0;i < n;i++){
            v[i].first *= -1;
        }
    }

    int minval = n+1;
    for(int i = 0;i < n;i++){
        minval = min(minval,v[i].first);
    }
    int diff = 1 - minval;
    for(int i = 0;i < n;i++){
        v[i].first += diff;
    }
	for(int i = 0;i < n;i++){
        //printf("%d %d\n",v[i].first,v[i].second);
        answer(v[i].second,v[i].first);
	}

}

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