Submission #1061976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061976		1ne	Xylophone (JOI18_xylophone)	C++17	0 / 100	0 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;
    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 (stderr)

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];
      |            ^

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