Submission #67549

#	Time	Username	Problem	Language	Result	Execution time	Memory
67549		JustasZ	Xylophone (JOI18_xylophone)	C++14	100 / 100	119 ms	856 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int>pii;
const int maxn=1e5+100;
/*int query(int l, int r)
{
    cout<<l<<" "<<r<<endl;
    int ret;
    cin>>ret;
    return ret;
}*/
void solve(int n)
{
    int arr[maxn];
    int two[maxn], three[maxn], sgn[maxn];
    for(int i=1; i<=n-1; i++)
        two[i]=query(i, i+1);
    for(int i=1; i<=n-2; i++)
        three[i]=query(i, i+2);
    if(three[1]==two[1]+two[2])
        sgn[1]=sgn[2]=1;
    else sgn[1]=1, sgn[2]=-1;
    for(int i=3; i<=n-1; i++)
    {
        if(two[i-1]+two[i]!=three[i-1])
            sgn[i]=-sgn[i-1];
        else sgn[i]=sgn[i-1];
    }
    arr[1]=1;
    int mn=INT_MAX;
    for(int i=2; i<=n; i++)
    {
        arr[i]=arr[i-1]+sgn[i-1]*two[i-1];
        mn=min(mn, arr[i]);
    }
    int add=1-mn;
    if(mn<=0)
    for(int i=1; i<=n; i++)
        arr[i]+=add;
    for(int i=1; i<=n; i++)
    {
        if(arr[i]==1)break;
        if(arr[i]==n)
        {
            for(int j=1; j<=n; j++)
                arr[j]=n-arr[j]+1;
            break;
        }
    }
    for(int i=1; i<=n; i++)
        answer(i, arr[i]);
    //for(int i=1; i<=n; i++)
    //    cout<<arr[i]<<" ";
}
/*int main()
{
    solve(4);
}*/

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