Submission #641886

#	Time	Username	Problem	Language	Result	Execution time	Memory
641886		ivaziva	Xylophone (JOI18_xylophone)	C++14	100 / 100	106 ms	488 KiB

xylophone

    #include "xylophone.h"
    #include <bits/stdc++.h>
    #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
    #define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
    typedef long long ll;
    typedef std::pair<int, int> pii;
    typedef std::pair<ll , ll > pll;
    using namespace std;
     
    const int N = 5010;
    static int a[N];
    static int d1[N], d2[N], e[N];
     
    void solve(int n)
    {
    	Loop (i,0,n-1)
    		d1[i] = query(i+1, i+2);
    	Loop (i,0,n-2)
    		d2[i] = query(i+1, i+3);
    	e[0] = d1[0];
    	Loop (i,1,n-1) {
    		e[i] = d1[i];
    		if (e[i-1] < 0)
    			e[i] = -e[i];
    		if (d1[i-1] + d1[i] != d2[i-1])
    			e[i] = -e[i];
    	}
    	int mn = 0, mni = 0, cur = 0;
    	Loop (i,1,n) {
    		cur += e[i-1];
    		if (cur < mn) {
    			mni = i;
    			mn = cur;
    		}
    	}
    	cur = 0;
    	Loop (i,mni,n) {
    		a[i] = cur;
    		cur += e[i];
    	}
    	cur = 0;
    	LoopR (i,0,mni) {
    		cur -= e[i];
    		a[i] = cur;
    	}
    	int pos_n = 0;
    	while (a[pos_n] != n-1)
    		++pos_n;
    	if (mni > pos_n) {
    		Loop (i,0,n)
    			a[i] = n-1-a[i];
    	}
    	Loop (i,0,n)
    		answer(i+1, a[i]+1);
    }

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