답안 #890780

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
890780 2023-12-22T03:10:57 Z vjudge1 Bitaro's travel (JOI23_travel) C++17
15 / 100
20 ms 4308 KB
/*
 
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);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -