# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
763249 | CESxRhino | Xylophone (JOI18_xylophone) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "xylophone.h"
#include <bits/stdc++.h>
#define s second
#define pb push_back
#define int long long
#define endl '\n'
using namespace std;
const int MAXN = 1e18;
int mod = 1e9 + 7;
int re[200005];
int next1[200005];
int next2[200005];
void solve(int N)
{
for(int i = 1;i <= N - 1;i++)
{
next1[i] = query(i,i + 1);
}
for(int i = 1;i <= N - 2;i++)
{
next2[i] = query(i,i + 2);
}
re[1] = 1;
for(int i = 1;i <= N - 2;i++)
{
if(next1[i] + next1[i + 1] == next2[i])
{
re[i + 1] = re[i];
}
else
{
re[i + 1] = -re[i];
}
}
next1[N] = 0;
int Min = 0;
for(int i = N - 1;i >= 1;i--)
{
next1[i] = next1[i + 1] - re[i] * next1[i];
Min = min(Min,next1[i]);
}
for(int i = 1;i <= N;i++)
{
next1[i] = next1[i] - Min + 1;
}
for(int i = 1;i <= N;i++)
{
if(next1[i] == 1)
{
break;
}
if(next1[i] == N)
{
for(int j = 1;j <= N;j++)
{
next1[j] = N + 1 - next1[j];
}
}
}
for(int i = 1;i <= N;i++)
{
answer(i,next1[i]);
}
cout << endl;
}