Submission #931262

#	Time	Username	Problem	Language	Result	Execution time	Memory
931262		Baizho	Xylophone (JOI18_xylophone)	C++14	100 / 100	50 ms	592 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
 
// #pragma GCC optimize("Ofast,unroll-loops,fast-math")
// #pragma GCC target("popcnt")
 
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
 
#define sz size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define pb push_back
 
const int mod = ll(1e9)+7; //(b + (a%b)) % b (to mod -1%(10^9+7) correctly in c++ its -1 but its suppose to be 10^9+6
const ll MOD = 998244353;  // (a%mod)*(binpow(b,mod-2,mod) = (a/b)%mod
const long long inf = 5e18;
const long double eps = 1e-15L;
 
ll lcm(ll a, ll b) { return (a / __gcd(a,b))*b; }
 
ll binpow(ll a, ll b, ll m) { ll res=1; a %= m; while(b>0){ if(b&1)res=(res * a) % m; a=(a * a) % m; b/=2; } return res%m;}
 
void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }

int query(int s, int t);
void answer(int i, int a);

void solve(int N) {
	int n = N;
	int a[N + 1], d[N];
	vector<bool> vis(n + 1);
	for(int i = 1; i < N; i ++) d[i] = query(i, i + 1);
	int l = 2, r = N, posn;
	while(l <= r) {
		int mid = (l + r) / 2;
		if(query(1, mid) == N - 1) r = mid - 1, posn = mid;
		else l = mid + 1;
	}
	a[posn] = N;
	vis[a[posn]] = 1;
	a[posn - 1] = N - d[posn - 1];
	vis[a[posn - 1]] = 1;
	if(posn + 1 <= N) {
		a[posn + 1] = N - d[posn];
		vis[a[posn + 1]] = 1;
	}
	for(int i = posn + 2; i <= N; i ++) {
		int c = d[i - 1];
		if(c + a[i - 1] > n || vis[c + a[i - 1]]) {
			a[i] = a[i - 1] - c;
			continue;
		}
		if(- c + a[i - 1] < 1 || - c + a[i - 1] > n || vis[- c + a[i - 1]]) {
			a[i] = a[i - 1] + c;
			continue;
		}
		int b = query(i - 2, i);
		if(b + min(a[i - 2], a[i - 1]) == c + a[i - 1]) {
			a[i] = c + a[i - 1];
		} else if(max(a[i - 2], a[i - 1]) - b == a[i - 1] - c) {
			a[i] = a[i - 1] - c;
		} else if(a[i - 1] < a[i - 2]) {
			a[i] = a[i - 1] + c;
		} else a[i] = a[i - 1] - c;
		vis[a[i]] = 1;
	}
	for(int i = posn - 2; i >= 1; i --) {
		int c = d[i];
		if(c + a[i + 1] > n || vis[c + a[i + 1]]) {
			a[i] = a[i + 1] - c;
			continue;
		}
		if(- c + a[i + 1] < 1 || - c + a[i + 1] > n || vis[- c + a[i + 1]]) {
			a[i] = a[i + 1] + c;
			continue;
		}
		int b = query(i, i + 2);
		if(b + min(a[i + 2], a[i + 1]) == c + a[i + 1]) {
			a[i] = c + a[i + 1];
		} else if(max(a[i + 2], a[i + 1]) - b == a[i + 1] - c) {
			a[i] = a[i + 1] - c;
		} else if(a[i + 1] < a[i + 2]) {
			a[i] = a[i + 1] + c;
		} else a[i] = a[i + 1] - c;
		vis[a[i]] = 1;
	}
	for(int i = 1; i <= N; i ++) {
//		cout<<a[i]<<endl;
		answer(i, a[i]);
	}
}

Compilation message (stderr)

xylophone.cpp: In function 'void Freopen(std::string)':
xylophone.cpp:34:34: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
xylophone.cpp:34:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:55:27: warning: 'posn' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |   a[posn + 1] = N - d[posn];
      |                     ~~~~~~^

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