QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#747442 | #5481. Beast Bullies | rahulmnavneeth | AC ✓ | 63ms | 7084kb | C++17 | 4.2kb | 2024-11-14 17:10:43 | 2024-11-14 17:10:43 |
Judging History
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'