Submission #1045545

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

xylophone

#include <bits/stdc++.h>
#include "xylophone.h"
#include <ext/pb_ds/assoc_container.hpp> 
 
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
 
using namespace std;
using namespace __gnu_pbds;
 
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define f first
#define s second
//~ #define int long long
#define ll long long
#define pii pair<int,int>
#define ar array
 
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
 
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
 tree_order_statistics_node_update> ordered_set;
 
const int inf = 1e17 + 7;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;
const int md = 998244353;
 
int binpow(int a, int b){
	if(b == 0)return 1;
	if(b % 2 == 0){
		int c = binpow(a,b/2);
		return (c*c)%mod;
	}
	return (binpow(a,b-1)*a)%mod;
}
 
int divi(int a, int b){
	return (a*(binpow(b,mod-2)))%mod;
}
 
int n,m,k;
 
void solve(int n){
	
	vector<int>v(n+1);
	//~ for(int i = 1;i<n;i++){
		//~ v[i] = quer
	//~ }
	
	int l = 2, r = n, pos = n;
	while(l <= r){
		int mid = (l+r) / 2;
		int h = query(1,mid);
		//~ cout << 1 << " " << mid << endl;
		//~ int h;
		//~ cin >> h;	
		if(h == n-1){ 
			pos = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	
	//~ cout << pos << "\n";
	
	vector<int>ans(n+1);
	map<int,int>vis;
	ans[pos] = n;
	vis[n] = 1;
	
	int h, u;
	
	h = query(pos - 1, pos);
	//~ cout << pos - 1 << " " << pos << endl;
	//~ cin >> h;
	ans[pos - 1] = n - h;
	vis[n - h] = 1;
	v[pos - 1] = h;
	
	if(pos < n){
		h = query(pos, pos + 1);
		//~ cout << pos << " " << pos + 1 << endl;
		//~ cin >> h;
		ans[pos + 1] = n - h;
		vis[n - h] = 1;
		v[pos] = h;
	}
	
	bool flag = true;
	
	for(l = pos - 2; l>=1; l--){
		h = query(l, l+1);
		//~ cout << l << " " << l + 1 << endl;
		//~ cin >> h;
		v[l] = h;
		
		if(vis[ans[l+1]+h] == 1 || ans[l+1] + h > n){
			ans[l] = ans[l+1] - h;
			vis[ans[l+1] - h] = 1;
			flag = true;
			continue;
		}
		
		if(vis[ans[l+1]-h] == 1 || ans[l+1] - h < 1){
			ans[l] = ans[l+1] + h;
			vis[ans[l+1] + h] = 1;
			flag = false;
			continue;
		}
		
		if(flag){
			u = query(l, l + 2);
			//~ cout << l << " " << l + 2 << endl;
			//~ cin	>> u;
			
			if(v[l+1] + h != u){
				ans[l] = ans[l+1] + h;
				vis[ans[l+1] + h] = 1;
				flag = false;
			}
			else{
				ans[l] = ans[l+1] - h;
				vis[ans[l+1] - h] = 1;
				flag = true;
			}
		}
		
		else if(!flag){
			u = query(l, l + 2);
			//~ cout << l << " " << l + 2 << endl;
			//~ cin >> u;
			
			if(v[l+1] + u == h){
				ans[l] = ans[l+1] - h;
				vis[ans[l+1] - h] = 1;
				flag = true;
			}
			else{
				ans[l] = ans[l+1] + h;
				vis[ans[l+1] + h] = 1;
				flag = false;
			}
		}
	}
	
	//-------------------------------------------------------------------------
	flag = true;
	
	for(l = pos + 2; l <= n; l++){
		h = query(l-1, l);
		//~ cout << l - 1 << " " << l << endl;
		//~ cin >> h;
		v[l] = h;
		
		if(vis[ans[l-1]+h] == 1 || ans[l-1] + h > n){
			ans[l] = ans[l-1] - h;
			vis[ans[l-1] - h] = 1;
			flag = true;
			continue;
		}
		
		if(vis[ans[l-1]-h] == 1 || ans[l-1] - h < 1){
			ans[l] = ans[l-1] + h;
			vis[ans[l-1] + h] = 1;
			flag = false;
			continue;
		}
		
		if(flag){
			u = query(l-2, l);
			//~ cout << l - 2<< " " << l << endl;
			//~ cin	>> u;
			
			if(v[l-1] + h != u){
				ans[l] = ans[l-1] + h;
				vis[ans[l-1] + h] = 1;
				flag = false;
			}
			else{
				ans[l] = ans[l-1] - h;
				vis[ans[l-1] - h] = 1;
				flag = true;
			}
		}
		
		else if(!flag){
			u = query(l-2, l);
			//~ cout << l - 2 << " " << l << endl;
			//~ cin >> u;
			
			if(v[l-1] + u == h){
				ans[l] = ans[l-1] - h;
				vis[ans[l-1] - h] = 1;
				flag = true;
			}
			else{
				ans[l] = ans[l-1] + h;
				vis[ans[l-1] + h] = 1;
				flag = false;
			}
		}
	}
	
	for(int i = 1;i<=n;i++)answer(i, ans[i]);
	return;
}
/*
 
*/
 //~ signed main()
//~ {
//	freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
	//~ ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	//~ int tt=1;//cin>>tt;
	//~ while(tt--)solve(5);
 
//~ }
 

Compilation message (stderr)

xylophone.cpp:27:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+17' to '2147483647' [-Woverflow]
   27 | const int inf = 1e17 + 7;
      |                 ~~~~~^~~

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