| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1061978 |
2024-08-16T16:13:05 Z |
1ne |
Xylophone (JOI18_xylophone) |
C++17 |
|
50 ms |
600 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 + 1;
}
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 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
2 ms |
344 KB |
Output is correct |
| 6 |
Correct |
2 ms |
344 KB |
Output is correct |
| 7 |
Correct |
2 ms |
344 KB |
Output is correct |
| 8 |
Correct |
1 ms |
344 KB |
Output is correct |
| 9 |
Correct |
2 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
344 KB |
Output is correct |
| 11 |
Correct |
1 ms |
344 KB |
Output is correct |
| 12 |
Correct |
1 ms |
344 KB |
Output is correct |
| 13 |
Correct |
1 ms |
344 KB |
Output is correct |
| 14 |
Correct |
1 ms |
344 KB |
Output is correct |
| 15 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
2 ms |
344 KB |
Output is correct |
| 6 |
Correct |
2 ms |
344 KB |
Output is correct |
| 7 |
Correct |
2 ms |
344 KB |
Output is correct |
| 8 |
Correct |
1 ms |
344 KB |
Output is correct |
| 9 |
Correct |
2 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
344 KB |
Output is correct |
| 11 |
Correct |
1 ms |
344 KB |
Output is correct |
| 12 |
Correct |
1 ms |
344 KB |
Output is correct |
| 13 |
Correct |
1 ms |
344 KB |
Output is correct |
| 14 |
Correct |
1 ms |
344 KB |
Output is correct |
| 15 |
Correct |
1 ms |
344 KB |
Output is correct |
| 16 |
Correct |
2 ms |
344 KB |
Output is correct |
| 17 |
Correct |
5 ms |
344 KB |
Output is correct |
| 18 |
Correct |
8 ms |
444 KB |
Output is correct |
| 19 |
Correct |
8 ms |
444 KB |
Output is correct |
| 20 |
Correct |
8 ms |
344 KB |
Output is correct |
| 21 |
Correct |
11 ms |
420 KB |
Output is correct |
| 22 |
Correct |
12 ms |
344 KB |
Output is correct |
| 23 |
Correct |
6 ms |
344 KB |
Output is correct |
| 24 |
Correct |
9 ms |
440 KB |
Output is correct |
| 25 |
Correct |
9 ms |
444 KB |
Output is correct |
| 26 |
Correct |
9 ms |
344 KB |
Output is correct |
| 27 |
Correct |
9 ms |
344 KB |
Output is correct |
| 28 |
Correct |
9 ms |
440 KB |
Output is correct |
| 29 |
Correct |
11 ms |
600 KB |
Output is correct |
| 30 |
Correct |
10 ms |
444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
2 ms |
344 KB |
Output is correct |
| 6 |
Correct |
2 ms |
344 KB |
Output is correct |
| 7 |
Correct |
2 ms |
344 KB |
Output is correct |
| 8 |
Correct |
1 ms |
344 KB |
Output is correct |
| 9 |
Correct |
2 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
344 KB |
Output is correct |
| 11 |
Correct |
1 ms |
344 KB |
Output is correct |
| 12 |
Correct |
1 ms |
344 KB |
Output is correct |
| 13 |
Correct |
1 ms |
344 KB |
Output is correct |
| 14 |
Correct |
1 ms |
344 KB |
Output is correct |
| 15 |
Correct |
1 ms |
344 KB |
Output is correct |
| 16 |
Correct |
2 ms |
344 KB |
Output is correct |
| 17 |
Correct |
5 ms |
344 KB |
Output is correct |
| 18 |
Correct |
8 ms |
444 KB |
Output is correct |
| 19 |
Correct |
8 ms |
444 KB |
Output is correct |
| 20 |
Correct |
8 ms |
344 KB |
Output is correct |
| 21 |
Correct |
11 ms |
420 KB |
Output is correct |
| 22 |
Correct |
12 ms |
344 KB |
Output is correct |
| 23 |
Correct |
6 ms |
344 KB |
Output is correct |
| 24 |
Correct |
9 ms |
440 KB |
Output is correct |
| 25 |
Correct |
9 ms |
444 KB |
Output is correct |
| 26 |
Correct |
9 ms |
344 KB |
Output is correct |
| 27 |
Correct |
9 ms |
344 KB |
Output is correct |
| 28 |
Correct |
9 ms |
440 KB |
Output is correct |
| 29 |
Correct |
11 ms |
600 KB |
Output is correct |
| 30 |
Correct |
10 ms |
444 KB |
Output is correct |
| 31 |
Correct |
20 ms |
344 KB |
Output is correct |
| 32 |
Correct |
33 ms |
448 KB |
Output is correct |
| 33 |
Correct |
47 ms |
444 KB |
Output is correct |
| 34 |
Incorrect |
50 ms |
344 KB |
Wrong Answer [2] |
| 35 |
Halted |
0 ms |
0 KB |
- |
