# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
433956 | LouayFarah | Xylophone (JOI18_xylophone) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
#include "xylophone.h"
using namespace std;
#define pb push_back
void solve(int n)
{
/*orig.resize(n+1);
for(int i = 1; i<=n; i++)
cin >> orig[i];*/
vector<vector<ll>> q(n+1, vector<ll>(n+1, 0));
for(int i = 1; i<n; i++)
{
q[i][i+1] = query(i, i+1);
}
for(int i = 1; i<n-1;i++)
{
q[i][i+2] = query(i, i+2);
}
vector<int> arr(n+1);
arr[1] = 1;
for(int i = 1; i<n-1; i++)
{
if(q[i][i+2]==q[i][i+1]+q[i+1][i+2])
{
arr[i+1] = arr[i];
}
else
{
arr[i+1]-=arr[i];
}
}
for(int i = 1; i<n; i++)
{
arr[i]*=q[i][i+1];
}
vector<int> res(n+1);
res[1] = 1;
for(int i = 1; i<n; i++)
{
res[i+1] = res[i] + arr[i];
}
int mini = 1e9;
for(int i = 1; i<=n; i++)
mini = min(mini, res[i]);
for(int i = 1; i<=n; i++)
{
res[i]-=mini;
res[i]--;
}
bool flag = true;
int l = n, r = 1;
for(int i = 1; i<=n; i++)
{
if(res[i]<=0)
{
flag = false;
break;
}
if(res[i]==1)
l = i;
if(res[i]==n)
r = i;
}
if(l>=r)
flag = false;
if(flag)
{
for(int i = 1; i<=n; i++)
answer(i, res[i]);
}
else
{
//res.assign(n+1, 1);
for(int i = 1; i<n; i++)
res[i+1] = res[i] - arr[i];
int mini = 1e9;
for(int i = 1; i<=n; i++)
mini = min(mini, res[i]);
for(int i = 1; i<=n; i++)
{
res[i]-=mini;
res[i]--;
}
for(int i = 1; i<=n; i++)
mini = min(mini, res[i]);
int dif = 1 - mini;
for(int i = 1; i<=n; i++)
res[i]+=dif;
for(int i = 1; i<=n; i++)
answer(i, res[i]);
}
}