| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1061976 |
2024-08-16T16:12:42 Z |
1ne |
Xylophone (JOI18_xylophone) |
C++17 |
|
0 ms |
344 KB |
#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
static int A[5000];
void solve(int N) {
int i = 1;
int left = 1,right = N;
while(left<=right){
int mid = (left + right)>>1;
if (query(mid,N) == N - 1){
left = mid + 1;
i = mid;
}
else right = mid - 1;
}
//answer(i - 1,1);
int pos = i - 1;
int mn = 1,vv = 1;
vector<int>ans(N + 1,-1);
ans[i - 1] = 1;
vector<int>got(N + 1,0);
for (int j = i - 2;j>=1;--j){
if (j == i - 2){
int v1 = query(j,i - 1);
got[v1] = 1;
ans[j] = v1 + 1;
}
else{
int v1 = query(j,pos);
int v2 = query(j,j + 1);
if (got[v1]){
//value is less than prev and greater than mn
//value is greater than prev and lesser than mn
if (ans[j + 1] - ans[pos] > 0){
ans[j] = ans[j + 1] - v2;
}
else{
ans[j] = ans[j + 1] + v2;
}
pos = j + 1;
for (int k = 0;k<=N;++k)got[k] = 0;
got[v2] = 1;
}
else{
if (ans[j + 1] - ans[pos] > 0){
//increasing seq
if (v1 > v2){
ans[j] = ans[j + 1] + v2;
got[v1] = 1;
}
else{
ans[j] = ans[j + 1] - v2;
for (int k = 0;k<=N;++k){
got[k] = 0;
}
got[v2] = 1;
pos = j + 1;
}
}
else{
if (v1 > v2){
ans[j] = ans[j + 1] - v2;
got[v1] = 1;
}
else{
ans[j] = ans[j + 1] + v2;
for (int k = 0;k<=N;++k){
got[k] = 0;
}
got[v2] = 1;
pos = j + 1;
}
}
}
}
}
for (int k = 0;k<=N;++k){
got[k] = 0;
}
pos = i - 1;
for (int j = i;j<=N;++j){
if (j == i){
int v1 = query(i - 1,j);
got[v1] = 1;
ans[j] = v1 + 1;
}
else{
int v1 = query(pos,j);
int v2 = query(j - 1,j);
if (got[v1]){
//value is less than prev and greater than mn
//value is greater than prev and lesser than mn
if (ans[j - 1] - ans[pos] > 0){
//increasing sequence
ans[j] = ans[j - 1] - v2;
}
else{
//decreasing sequence
ans[j] = ans[j - 1] + v2;
}
pos = j - 1;
for (int k = 0;k<=N;++k)got[k] = 0;
got[v2] = 1;
}
else{
if (ans[j - 1] - ans[pos] > 0){
//increasing seq
if (v1 > v2){
ans[j] = ans[j - 1] + v2;
got[v1] = 1;
}
else{
ans[j] = ans[j - 1] - v2;
for (int k = 0;k<=N;++k){
got[k] = 0;
}
got[v2] = 1;
pos = j - 1;
}
}
else{
//decreasing seq
if (v1 > v2){
ans[j] = ans[j - 1] - v2;
got[v1] = 1;
}
else{
ans[j] = ans[j - 1] + v2;
for (int k = 0;k<=N;++k){
got[k] = 0;
}
got[v2] = 1;
pos = j - 1;
}
}
}
}
}
for (int i = 1;i<=N;++i)answer(i,ans[i]);
}
Compilation message
xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:20:9: warning: unused variable 'mn' [-Wunused-variable]
20 | int mn = 1,vv = 1;
| ^~
xylophone.cpp:20:16: warning: unused variable 'vv' [-Wunused-variable]
20 | int mn = 1,vv = 1;
| ^~
xylophone.cpp: At global scope:
xylophone.cpp:4:12: warning: 'A' defined but not used [-Wunused-variable]
4 | static int A[5000];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
