QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#747442#5481. Beast BulliesrahulmnavneethAC ✓63ms7084kbC++174.2kb2024-11-14 17:10:432024-11-14 17:10:43

Judging History

你现在查看的是最新测评结果

  • [2024-11-14 17:10:43]
  • 评测
  • 测评结果:AC
  • 用时:63ms
  • 内存:7084kb
  • [2024-11-14 17:10:43]
  • 提交

answer

/*
        File: icpc-mock-141124-A-a_main.cpp
        Date and Time Created: 2024-11-14 14:33:26
        Author: Rahul M. Navneeth
*/

/* ----------------- HEADER FILES ----------------- */

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

/* ----------------- NAMESPACE ----------------- */

using namespace std;
using namespace chrono;
using namespace __gnu_pbds;

/* ----------------- TEMPLATES ------------------ */

/* clang-format off */

// MACROS
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define io freopen("./input.txt", "r", stdin); freopen("./output.txt", "w", stdout); freopen("./output.txt", "w", stderr);

// TYPEDEF
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds; // POLICY BASED DS

// SHORTCUTS
#define ar array
#define pb push_back
#define pob pop_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define F first
#define S second
#define UNIQUE_SORT(v) sort(all(v)); v.erase(unique(all(v)), v.end())

// FUNCTIONS
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void swap(int &x, int &y) { int temp = x; x = y; y = temp; }
ll combination(ll n, ll r, ll m, ll *fact, ll *ifact) { ll val1 = fact[n]; ll val2 = ifact[n - r]; ll val3 = ifact[r]; return (((val1 * val2) % m) * val3) % m; }
bool revsort(ll a, ll b) {return a > b;}
ll phin(ll n) {ll number = n; if (n % 2 == 0) {number /= 2; while (n % 2 == 0) n /= 2;} for (ll i = 3; i <= sqrt(n); i += 2) {if (n % i == 0) {while (n % i == 0)n /= i; number = (number / i * (i - 1));}} if (n > 1)number = (number / n * (n - 1)) ; return number;} //O(sqrt(N))
ll getRandomNumber(ll l, ll r) {return uniform_int_distribution<ll>(l, r)(rng);} 
vector<ll> sieve(int n) {int*arr = new int[n + 1](); vector<ll> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
ll modpow(ll a, ll b, ll MOD) { ll res = 1; while(b > 0) { if(b & 1) { res = (res * a) % MOD; } b = b >> 1; a = (a*a) % MOD; } return res; }
void extendgcd(ll a, ll b, ll *v) { if (b == 0) { v[0] = 1; v[1] = 0; v[2] = a; return; }
extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return; } // PASS AN ARRY OF SIZE1 3
ll mminv(ll a, ll b) { ll arr[3]; extendgcd(a, b, arr); return arr[0]; } // FOR NON PRIME B
ll mminvprime(ll a, ll b) { return modpow(a, b - 2, b); }
ll mod_add(ll a, ll b, ll m) { a = a % m; b = b % m; return (((a + b) % m) + m) % m; }
ll mod_mul(ll a, ll b, ll m) { a = a % m; b = b % m; return (((a * b) % m) + m) % m; }
ll mod_sub(ll a, ll b, ll m) { a = a % m; b = b % m; return (((a - b) % m) + m) % m; }
ll mod_div(ll a, ll b, ll m) { a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m; } // ONLY FOR PRIME M
void precision(int a) { cout << setprecision(a) << fixed; }

// CONSTANTS
const float PI = 3.141592653589793238462;
const int MOD = 1e9 + 7;
const int mxn = 1e7;
const int LOG = 30;

/* --------------------- CODE BEGINS ---------------------- */

void solve() {
	ll N; cin >> N;
	vector<ll> a(N); for(ll i = 0 ; i < N; i++) cin >> a[i];
	sort(all(a)); reverse(all(a));
	ll x = 0;
	ll i = 0;
	ll c = 0;
	while(i < N) {
		ll y = a[i];
		while(i + 1 < N && y < x) {
			i++;
			y += a[i];
		}
		if(y >= x) {
			c = i;
			x += y;
		}
		i++;
	}
	cout << c+1 << "\n";
    return;
}

/*---------------------- MAIN DRIVER ------------------------*/

// MAIN
int32_t main() {
  fast_io
  #ifndef ONLINE_JUDGE
    io;
  #endif
  high_resolution_clock::time_point start, end;
  #ifndef ONLINE_JUDGE
    start = chrono::high_resolution_clock::now();
  #endif
  int t = 1;
  int i = 1;
  // cin >> t;
  while (i <= t) {
  	#ifndef ONLINE_JUDGE
		cout << "TESTCASE #" << i << "\n";
	#endif
	i++;
    solve();
  }
  #ifndef ONLINE_JUDGE
    end = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::milliseconds>(end - start);
    cout << "-------------\nRUNTIME: " << duration.count() << " ms\n";
  #endif
  return 0;
}

/* clang-format on */

詳細信息

Test #1:

score: 100
Accepted
time: 60ms
memory: 6968kb

input:

500000
976631732
51389671
729809897
630844317
294721017
903231515
477913449
871071076
636104080
345822085
97441187
499323378
522845426
310022664
199310190
776622973
602672555
646874222
214723272
285341530
962727359
681361226
47426538
272153520
693133904
542337627
556307610
325596239
95738088
5495543...

output:

155101

result:

ok single line: '155101'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

4
3
4
8
9

output:

3

result:

ok single line: '3'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

8
20
1
2
13
9
5
8
61

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

1
10

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 53ms
memory: 7036kb

input:

500000
488349
25720
365654
316274
147722
452008
239786
436076
318835
173398
49102
250556
262275
155533
100095
388891
302219
324219
107768
143112
481547
341758
23696
136464
347550
272004
279048
163397
48247
275611
118344
461362
410109
2256
76615
358107
240210
265807
435838
408622
38878
336952
171230
...

output:

154891

result:

ok single line: '154891'

Test #6:

score: 0
Accepted
time: 62ms
memory: 6972kb

input:

500000
999511652
999974281
999634347
999683727
999852279
999547993
999760215
999563925
999681166
999826603
999950899
999749445
999737726
999844468
999899906
999611110
999697782
999675782
999892233
999856889
999518454
999658243
999976305
999863537
999652451
999727997
999720953
999836604
999951754
999...

output:

262172

result:

ok single line: '262172'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3512kb

input:

30
16
268435456
2048
32768
16777216
65536
131072
536870912
67108864
512
8
4194304
524288
4
1
8388608
33554432
262144
8192
256
32
2097152
128
4096
16384
1048576
134217728
64
1024
2

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 63ms
memory: 7012kb

input:

500000
976652749
51071855
732379151
633144920
294813539
904339860
479425162
872870196
638243905
346103305
97915062
501226286
524611259
310395471
199822607
779333750
605147990
648957289
215290850
285495798
962916507
684091230
47001297
272454876
695820020
543917748
558282177
326357439
96212988
5512266...

output:

154742

result:

ok single line: '154742'

Test #9:

score: 0
Accepted
time: 58ms
memory: 7084kb

input:

500000
653912
25720
370223
316974
147722
503094
239791
469456
319623
173398
49102
250570
262309
155533
100095
398057
302581
325201
107768
143112
606296
343747
23696
136464
350034
272070
279150
163397
48247
275690
118344
527503
426964
2256
76615
361714
240215
265850
469055
424778
38878
338612
171230
...

output:

190555

result:

ok single line: '190555'

Test #10:

score: 0
Accepted
time: 50ms
memory: 7056kb

input:

500000
655230
25720
370212
316954
147722
502533
239789
469006
319615
173398
49102
250563
262302
155533
100095
398151
302574
325220
107768
143112
607471
343694
23696
136464
349971
272058
279140
163397
48247
275679
118344
526711
426747
2256
76615
361671
240213
265842
468553
424623
38878
338570
171230
...

output:

200853

result:

ok single line: '200853'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

43
8
832040
233
1597
121393
24157817
4181
39088169
317811
3524578
9227465
165580141
10946
3
1
433494437
196418
6765
5702887
267914296
13
28657
34
377
987
701408733
514229
21
144
2
2178309
102334155
610
63245986
5
2584
1346269
14930352
89
46368
55
75025
17711

output:

3

result:

ok single line: '3'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

31
12
202383360
1544
24705
12648960
49410
98820
404766720
50595840
386
6
3162240
395280
3
1
6324480
25297920
197640
6176
193
24
1581120
96
3088
12352
790560
101191680
48
772
2
809533440

output:

1

result:

ok single line: '1'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

30
15
268435455
2047
32767
16777215
65535
131071
536870911
67108863
511
7
4194303
524287
3
1
8388607
33554431
262143
8191
255
31
2097151
127
4095
16383
1048575
134217727
63
1023
2

output:

1

result:

ok single line: '1'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

31
9
134217729
1025
16385
8388609
32769
65537
268435457
33554433
257
5
2097153
262145
3
1
4194305
16777217
131073
4097
129
17
1048577
65
2049
8193
524289
67108865
33
513
2
536870913

output:

26

result:

ok single line: '26'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3744kb

input:

31
12
199229440
1520
24320
12451840
48640
97280
398458880
49807360
380
6
3112960
389120
3
1
6225920
24903680
194560
6080
190
24
1556480
95
3040
12160
778240
99614720
48
760
2
796917759

output:

30

result:

ok single line: '30'