oj.uz

Submission #890982

# Submission time Handle Problem Language Result Execution time Memory
890982 2023-12-22T05:47:57 Z vjudge1 Bitaro's travel (JOI23_travel) C++17
5 / 100
 3000 ms 621444 KB 
#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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 197 ms 94616 KB Output is correct
3 Correct 286 ms 94592 KB Output is correct
4 Correct 208 ms 94712 KB Output is correct
5 Correct 607 ms 94680 KB Output is correct
6 Correct 207 ms 94736 KB Output is correct
7 Correct 195 ms 94804 KB Output is correct
8 Correct 1 ms 436 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 452 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 357 ms 94664 KB Output is correct
15 Correct 250 ms 94800 KB Output is correct
16 Correct 205 ms 94684 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 197 ms 94616 KB Output is correct
3 Correct 286 ms 94592 KB Output is correct
4 Correct 208 ms 94712 KB Output is correct
5 Correct 607 ms 94680 KB Output is correct
6 Correct 207 ms 94736 KB Output is correct
7 Correct 195 ms 94804 KB Output is correct
8 Correct 1 ms 436 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 452 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 357 ms 94664 KB Output is correct
15 Correct 250 ms 94800 KB Output is correct
16 Correct 205 ms 94684 KB Output is correct
17 Execution timed out 3053 ms 621444 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 197 ms 94616 KB Output is correct
3 Correct 286 ms 94592 KB Output is correct
4 Correct 208 ms 94712 KB Output is correct
5 Correct 607 ms 94680 KB Output is correct
6 Correct 207 ms 94736 KB Output is correct
7 Correct 195 ms 94804 KB Output is correct
8 Correct 1 ms 436 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 452 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 357 ms 94664 KB Output is correct
15 Correct 250 ms 94800 KB Output is correct
16 Correct 205 ms 94684 KB Output is correct
17 Execution timed out 3053 ms 621444 KB Time limit exceeded
18 Halted 0 ms 0 KB -