QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#947787 | #10011. Lottery | hungry# | WA | 0ms | 4096kb | C++20 | 2.1kb | 2025-03-22 17:30:33 | 2025-03-22 17:30:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
ll gcd(ll x, ll y){
if(!y) return x;
return gcd(y, x%y);
}
multiset<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*10){
bool hv = false;
for(int i = 1; i <= 300; i++){
if(ab[i].empty()) continue;
hv = true;
int y = ab[i][0];
if(!cnt|| dlt(i, y) < 0){
suma += i, sumb += y; ab[i].pop_front();
ch[i].insert(y);
}else{
int id = -1;
double now = 0.00;
for(int j = 1; j <= 300; j++){
if(!ch[j].size()) continue;
int yy = *ch[j].begin();
if(dlt(i-j, y-yy) < now) now = dlt(i-j, y-yy), id = j;
}
if(id != -1){
int yy = *ch[id].begin(); ch[id].erase(ch[id].begin());
ab[i].pop_front();
suma += (i-id), sumb += (y-yy);
ch[i].insert(y);
ab[i].push_front(yy);
}
}
del();
cnt++;
}
if(!hv) break;
}
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
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
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'