제출 #1247318

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247318		nub	Bitaro's travel (JOI23_travel)	C++20	100 / 100	367 ms	4188 KiB

travel

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define ci const int
#define cll const long long
#define cull const unsigned long long
#define cd const double
#define cld const long double
#define fi first
#define se second
#define psb push_back
#define ppb pop_back
#define psf push_front
#define ppf pop_front
#define ps push
#define pp pop
using namespace std;

string file_name = "";
string input_extension = "";
string output_extension = "";

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){
	return uniform_int_distribution<ll>(l, r)(rng);
}

ci inf = 1e9;
ci neginf = -1e9;
cll inf_ll = 1e18;
cll neginf_ll = -1e18;

ll mulmod(ll a, ll b, ll MOD = LLONG_MAX){
	return (a%MOD)*(b%MOD)%MOD;
}

ll binpow(ll a, ll b, ll MOD = LLONG_MAX){
	ll res = 1, t = a % MOD, exp = b;
	while (exp > 0){
		if (exp & 1) res = mulmod(res, t, MOD);
		t = mulmod(t, t, MOD);
		exp >>= 1;
	}
	return res;
}

ll invmod(ll a, ll MOD = LLONG_MAX){
	return binpow(a, MOD-2, MOD);
}

/*
It's ok to not get all the subtasks
Think of each subtask as a seperate problem
The goal is to get the most points
Solve if u can think of a method instantly
If not, skip and return later
Also, check your code on multiple test cases please
(If you're doing codeforces then fine, go ham on it)

Notes:
Remember to check for double counting
Always empty arrays that are not in global
Always try to find default value for everything
Check for the correct size
Remember to check to sort when doing greedy

"Losing a ton of points for no reason" counter: 7
*/

ci N = 2e5+5;
ll v[N];

void solve(){
	int n, q;
	cin >> n;
	for (int i=0; i<n; i++) cin >> v[i];
	cin >> q;
	ll s;
	while (q--){
		cin >> s;
		int it = lower_bound(v, v+n, s)-v;
		int l, r;
		if (it == n) l = r = n-1;
		else if (v[it] == s || it == 0) l = r = it;
		else if (v[it] - s < s - v[it-1]) l = r = it;
		else l = r = it-1;
		
		ll res = abs(s-v[l]);
		s = v[l];
		while (true){
			if (l == 0){
				res += abs(s-v[n-1]);
				break;
			}
			if (r == n-1){
				res += abs(s-v[0]);
				break;
			}
			
			int L = v[l-1], R = v[r+1];
			if (abs(s-L) <= abs(s-R)){
				int nxt = lower_bound(v, v+n, 2*s-R)-v;
				res += abs(s-v[nxt]);
				s = v[nxt];
				l = nxt;
			}
			else {
				int nxt = upper_bound(v, v+n, 2*s-L)-v-1;
				res += abs(s-v[nxt]);
				s = v[nxt];
				r = nxt;
			}
		}
		cout << res << "\n";
	}
}

int main(){
	if (file_name.size() > 0 && input_extension.size() > 0){
		freopen((file_name+input_extension).c_str(), "r", stdin);
	}
	if (file_name.size() > 0 && output_extension.size() > 0){
		freopen((file_name+output_extension).c_str(), "w", stdout);
	}
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int t=1;
//	cin >> t;
	while (t--) solve();
}

컴파일 시 표준 에러 (stderr) 메시지

travel.cpp: In function 'int main()':
travel.cpp:121:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |                 freopen((file_name+input_extension).c_str(), "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
travel.cpp:124:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |                 freopen((file_name+output_extension).c_str(), "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 55 / 55