Submission #1061061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061061		1ne	Xylophone (JOI18_xylophone)	C++17	0 / 100	1 ms	344 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
static int A[5000];

void solve(int N) {
    int i = 1;
    while(query(i,N) == N - 1){
    	++i;
    }
    //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){
    				ans[j] = ans[j + 1] + v2; 	
    			}
    			else{
    				ans[j] = ans[j + 1] - v2;		
    			}
    			got[v1] = 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){
    				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){
    				ans[j] = ans[j - 1] + v2; 	
    			}
    			else{
    				ans[j] = ans[j - 1] - v2;		
    			}
    			got[v1] = 1;
    		}                          
    	}
    }
    for (int i = 1;i<=N;++i)answer(i,ans[i]);
}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:13:9: warning: unused variable 'mn' [-Wunused-variable]
   13 |     int mn = 1,vv = 1;
      |         ^~
xylophone.cpp:13:16: warning: unused variable 'vv' [-Wunused-variable]
   13 |     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];
      |            ^

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