QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#947730#10011. Lotteryhungry#WA 1ms4096kbC++201.5kb2025-03-22 17:09:032025-03-22 17:09:04

Judging History

This is the latest submission verdict.

  • [2025-03-22 17:09:04]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 4096kb
  • [2025-03-22 17:09:03]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 i128;
typedef double db;
ll gcd(ll x, ll y){
    if(!y) return x;
    return gcd(y, x%y);
}
set<int> ch[310];
deque<int> ab[310];
int n;
ll r, s;
double suma, sumb;
double dlt(ll dx, ll dy){
    return dx+1.00*r*s/(sumb+dy)-1.00*r*s/sumb;
}
void del(){
    while(true){
        int id = -1;
        double now = 0;
        for(int i = 1; i <= 300; i++){
            if(ch[i].empty()) continue;
            int dy = *ch[i].begin();
            if(dlt(-i, -dy) < now) id = i, now = dlt(-i, -dy);
        }
        if(id == -1) break;
        int dy = *ch[id].begin(); ch[id].erase(ch[id].begin());
        suma -= id, sumb -= dy;
    }
}
int main(){
    scanf("%d%lld%lld", &n, &r, &s);
    for(int i = 1; i <= n; i++){
        int a, b; scanf("%d%d", &a, &b);
        ab[a].push_back(b);
    }
    for(int i = 1; i <= 300; i++) sort(ab[i].begin(), ab[i].end(), greater<int> ());
    int cnt = 0;
    while(cnt < n){
        for(int i = 1; i <= 300; i++){
            if(ab[i].empty()) continue;
            int y = ab[i][0]; ab[i].pop_front();
            if(!cnt|| dlt(i, y) < 0){
                suma += i, sumb += y;
                ch[i].insert(y);
                del();
            }
            cnt++;
        }
    }
    ll A = suma*sumb+r*s, B = sumb;
    ll g = gcd(A, B);
    printf("%lld %lld\n", A/g, B/g);
    return 0;
}
/*
3 11 3
1 3
2 7
5 13
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4096kb

input:

3 11 3
1 3
2 7
5 13

output:

63 10

result:

ok 2 number(s): "63 10"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 4096kb

input:

8 608515 751563
113 451
9 4537
19 3343
79 855
260 4457
59 1650
142 3631
239 788

output:

457355493985 19712

result:

wrong answer 1st numbers differ - expected: '914765325642', found: '457355493985'