QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#455806#7614. Boxeslamba holder (Maciej Sidor, Matei Tinca, Liudas Staniulis)#WA 69ms3616kbC++20764b2024-06-26 20:25:132024-06-26 20:25:14

Judging History

This is the latest submission verdict.

  • [2024-06-26 20:25:14]
  • Judged
  • Verdict: WA
  • Time: 69ms
  • Memory: 3616kb
  • [2024-06-26 20:25:13]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;



void solve(){
    int n;
    cin >> n;
    vector<long long>a(n);
    for(auto &x : a)cin >> x;
    sort(a.begin(), a.end(), greater());
    int l = 1, r = n;

    auto check = [&](int mid){
        long long space = 0;
        for(int i = 0; i < mid; i++)space += (a[i]/2);
        for(int i = mid; i < n; i++){
            if(space < a[i])return false;
            space -= a[i];
            space += a[i]/2;
        }
        return true;
    };
    while(l <= r){
        int mid = (l + r)/2;
        if(check(mid))r = mid - 1;
        else l = mid + 1;
    }
    cout << l << '\n';
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--)solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3616kb

input:

4
5
1 2 1 1 8
3
1 1 1
6
1 1 1 4 1 2
3
8 4 2

output:

1
3
3
1

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 69ms
memory: 3572kb

input:

500000
1
137438953472
1
8589934592
1
2048
1
1048576
1
68719476736
1
524288
1
8192
1
536870912
1
16777216
1
549755813888
1
268435456
1
524288
1
8589934592
1
32768
1
32768
1
32
1
131072
1
2
1
524288
1
34359738368
1
8589934592
1
8192
1
68719476736
1
8589934592
1
524288
1
268435456
1
68719476736
1
26214...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 500000 lines

Test #3:

score: -100
Wrong Answer
time: 43ms
memory: 3564kb

input:

1299
360
131072 4294967296 67108864 4294967296 1 16384 16384 16384 268435456 67108864 268435456 2048 4294967296 16384 64 16384 68719476736 4 524288 134217728 131072 131072 134217728 134217728 67108864 64 16384 2147483648 1024 4 64 131072 67108864 131072 134217728 2048 131072 134217728 17179869184 67...

output:

13
10
16
6
17
8
14
66
49
24
6
14
11
11
12
14
164
9
14
12
16
11
18
5
19
15
12
112
12
44
24
10
43
29
75
11
11
4
10
14
20
11
119
8
11
14
8
100
33
12
8
11
24
12
18
12
6
154
44
10
10
11
37
59
10
11
12
12
26
68
11
15
14
9
133
88
16
11
35
7
8
17
15
3
9
66
16
8
17
136
8
28
13
14
28
13
10
25
13
10
7
72
191
2...

result:

wrong answer 1st lines differ - expected: '17', found: '13'