Submission #890780

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
890780	2023-12-22T03:10:57 Z	vjudge1	Bitaro's travel (JOI23_travel)	C++17	15 / 100	20 ms	4308 KB

travel

/*
 
author : abushbandit
contest : ---
 
*/
 
#include "bits/stdc++.h"
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
 
using namespace std;
 
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ff first
#define ss second
#define pb push_back
#define rep(i,s,f) for(int i = s;i < f;i++)
 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
 
#pragma GCC optimize("Ofast,no-stack-protector,fast-math",3)
 
template <class type1>
	using ordered_multiset = tree <type1, null_type, less_equal <type1>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<pair<int,int>> vii;
typedef pair<int,int> pii;
 
const ll INF = 1e18;
const ll MOD7 = 1e9 + 7;
const ll MOD9 = 998244353;
const ld PI = acos(-1.0);
const int N = 1e6 + 6;
 
template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}
 
template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
    
}
 
int binpow (int a, int n) {
	int res = 1;
	while (n) {
		if (n & 1)
			res *= a;
		a *= a;
		n >>= 1;
	}
	return res;
}
 
void start_file(string file){
	freopen((file + ".in").c_str(),"r",stdin);
	freopen((file + ".out").c_str(),"w",stdout);
}

void solve() {
	
	int n;
	cin >> n;
	int a[n];
	rep(i,0,n){
		cin >> a[i];
	}
	int q;
	cin >> q;
	if(q == 1){
		int x;
		cin >> x;
		vector<int> b;
		rep(i,0,n){
			b.pb(x - a[i]);
		}
		sort(all(b));
		int lstp = INF,lstn = INF,cntp = 0,cntn = 0,sumn = 0,sump = 0;
		for(int i = 0;i < b.size();i++){
			if(b[i] >= 0){
				cntp++;
				if(cntp == 1){
					lstp = i;
				}
			} else{
				cntn++;
				lstn = i;
			}
		}
		int ans = 0,lst = -1,cntnp = 0,cntnn = 0;
		while(true){
			int mn = INF,t = 0;
			if(lstp < INF){
				if(chmin(mn,b[lstp] + sump)){
					t = 1;
				}
			}
			if(lstn < INF){
				if(chmin(mn,-b[lstn] + sumn)){
					t = -1;
				}
			}
			if(t == 1){
				ans += mn;
				sumn += mn;
				sump -= mn;
				cntnp++;
				if(cntnp == cntp){
					lstp = INF;
				} else{
					lstp++;
				}
			} else if(t == -1){
				ans += mn;
				sump += mn;
				sumn -= mn;
				cntnn++;
				if(cntnn == cntn){
					lstn = INF;
				} else{
					lstn--;
				}
			} else{
				break;
			}
		}
		cout << ans << "\n";
	} else{
		
	}
	
}

signed main() {
	
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	
	int t = 1;
//	cin >> t;
	while(t--){
		solve();
	}
 
}

Compilation message

travel.cpp: In function 'void solve()':
travel.cpp:98:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |   for(int i = 0;i < b.size();i++){
      |                 ~~^~~~~~~~~~
travel.cpp:109:15: warning: unused variable 'lst' [-Wunused-variable]
  109 |   int ans = 0,lst = -1,cntnp = 0,cntnn = 0;
      |               ^~~
travel.cpp: In function 'void start_file(std::string)':
travel.cpp:75:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  freopen((file + ".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
travel.cpp:76:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  freopen((file + ".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	19 ms	4052 KB	Output is correct
18	Correct	18 ms	4056 KB	Output is correct
19	Correct	19 ms	4188 KB	Output is correct
20	Correct	19 ms	4056 KB	Output is correct
21	Correct	18 ms	4188 KB	Output is correct
22	Correct	19 ms	4308 KB	Output is correct
23	Correct	18 ms	4056 KB	Output is correct
24	Correct	20 ms	4044 KB	Output is correct
25	Correct	18 ms	4056 KB	Output is correct
26	Correct	18 ms	4052 KB	Output is correct
27	Correct	18 ms	4056 KB	Output is correct
28	Correct	18 ms	4056 KB	Output is correct
29	Correct	19 ms	4184 KB	Output is correct
30	Correct	18 ms	4056 KB	Output is correct
31	Correct	18 ms	4056 KB	Output is correct

Subtask #3

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Incorrect	0 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	1 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	19 ms	4052 KB	Output is correct
18	Correct	18 ms	4056 KB	Output is correct
19	Correct	19 ms	4188 KB	Output is correct
20	Correct	19 ms	4056 KB	Output is correct
21	Correct	18 ms	4188 KB	Output is correct
22	Correct	19 ms	4308 KB	Output is correct
23	Correct	18 ms	4056 KB	Output is correct
24	Correct	20 ms	4044 KB	Output is correct
25	Correct	18 ms	4056 KB	Output is correct
26	Correct	18 ms	4052 KB	Output is correct
27	Correct	18 ms	4056 KB	Output is correct
28	Correct	18 ms	4056 KB	Output is correct
29	Correct	19 ms	4184 KB	Output is correct
30	Correct	18 ms	4056 KB	Output is correct
31	Correct	18 ms	4056 KB	Output is correct
32	Correct	0 ms	348 KB	Output is correct
33	Incorrect	0 ms	348 KB	Output isn't correct
34	Halted	0 ms	0 KB	-