Submission #890982

#	Time	Username	Problem	Language	Result	Execution time	Memory
890982		vjudge1	Bitaro's travel (JOI23_travel)	C++17	5 / 100	3053 ms	621444 KiB

travel

#include <bits/stdc++.h>
using namespace std;/*
<<<<It's never too late for a new beginning in your life>>>>
Today is hard
  tomorrow will worse
  but the day after tomorrow will be the sunshine..
 
HARD WORK BEATS TALENT WHEN TALENT DOESN'T WORK HARD............
Never give up  */
//The most CHALISHKANCHIK
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vii;
const long long N = 1e5+50, inf = 1e18, mod = 1e9+7;
void solve(){
	int n;
	cin >> n;
	set<int> ps, st;
	for(int i = 0; i < n; i++){
		int x;
		cin >> x;
		ps.insert(x);
	}
	st = ps;
	int q, x, ans = 0;
	cin >> q;
	map<pair<set<int>, int>, int> mp; 
	while(q--){
		cin >> x;
		while(!ps.empty()){
			if(mp[{ps, x}]){
				ans+=mp[{ps, x}];
				break;
			}
			mp[{ps,x}] = ans;
			auto l = ps.lower_bound(x);
			auto r = ps.upper_bound(x);
			if(l == ps.end() || *l > *--ps.end())l--;
			if(r == ps.end() || *r > *--ps.end())r--;
			if(l == r){
				if(l != ps.begin())l--;
				else if(r != --ps.end())r++;
			}
			//~ cout << *l << ' ' << *r << ' ' << x << '\n';
			//~ cout << abs(x-*l) << ' ' << abs(*r-x) << '\n';
			if(abs(x-*l) <= abs(*r-x)){
				ans += abs(x-*l);
				x = *l;
				ps.erase(*l);
			}else{
				ans += abs(*r-x);
				x = *r;
				ps.erase(*r);
			}
			//~ for(auto i:ps)cout << i << ' ';
			//~ cout << '\n';
		}
		cout << ans << '\n';
		ans = 0;
		ps = st;
	}
}
main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int t = 1;
	//~ cin >> t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

travel.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main(){
      | ^~~~

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