QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#590634 | #9347. Competition in Swiss-system | kevinshan | WA | 459ms | 4068kb | C++23 | 4.3kb | 2024-09-26 09:13:47 | 2024-09-26 09:13:47 |
Judging History
answer
#pragma GCC optimize("Ofast,O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define f first
#define s second
#define THIRD frac(1,3)
#define ZERO frac{0,0}
struct frac {
ll num;
ll den;
frac(ll n, ll d) {
if(d == 0) num = 0, den = 0;
else {
ll g = gcd(n,d);
assert(g != 0);
num = n/g;
den = d/g;
}
}
bool is_zero() { return den == 0; }
bool is_less() { return den == 0 || num * 3 <= den; }
frac get_div(ll tot) {
ll g = gcd(num, tot);
if(g == 0) return ZERO;
assert(g != 0);
return {num/g, (tot/g)*den};
}
void display() {
if(is_less()) cout<<"1/3 ";
else cout<<num<<"/"<<den<<" ";
}
};
frac adding(frac a, frac b) {
if(a.is_zero()) return b;
if(b.is_zero()) return a;
if(a.is_less()) a = THIRD;
if(b.is_less()) b = THIRD;
// cout<<a.num<<"|"<<a.den<<"\n";
// cout<<b.num<<"|"<<b.den<<"\n";
ll new_num = a.num * b.den + b.num * a.den;
ll new_den = a.den * b.den;
ll g = gcd(new_num, new_den);
assert(g != 0);
return {new_num/g, new_den/g};
}
struct match{
int p1, p2, w1, w2, d;
int tot() { return w1 + w2 + d; }
};
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
if (fopen("input.in", "r")) {
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
}
int t; cin>>t;
while(t--){
int n, M;
cin>>n>>M;
vector<vector<int>> opponents_played(n, vector<int>());
vector<ll> match_points(n);
vector<ll> game_points(n);
// tot_match_points = rounds * 3;
vector<ll> tot_game_points(n);
vector<int> ar(M+1);
for(int i=1; i<=M; i++) cin>>ar[i];
for(int rounds=1; rounds<=M; rounds++) {
ll tot_match_points = rounds;
vector<bool> played(n);
vector<match> matches;
for(int j=0; j<ar[rounds]; j++) {
match m = {0,0,0,0,0};
cin>>m.p1>>m.p2>>m.w1>>m.w2>>m.d;
m.p1--;
m.p2--;
matches.pb(m);
int winner = 0;
if(m.w1 > m.w2) winner = 1;
if(m.w1 < m.w2) winner = 2;
match_points[m.p1] += (winner == 1 ? 3 : 0) + (winner == 0 ? 1 : 0);
match_points[m.p2] += (winner == 2 ? 3 : 0) + (winner == 0 ? 1 : 0);
game_points[m.p1] += 3*m.w1 + m.d;
game_points[m.p2] += 3*m.w2 + m.d;
played[m.p1] = 1;
played[m.p2] = 1;
opponents_played[m.p1].pb(m.p2);
opponents_played[m.p2].pb(m.p1);
tot_game_points[m.p1] += m.tot();
tot_game_points[m.p2] += m.tot();
}
for(int j=0; j<n; j++) {
if(!played[j]){
tot_game_points[j] += 2;
match_points[j] += 3;
game_points[j] += 6;
}
}
cout<<"Round "<<rounds<<"\n";
vector<frac> MWP(n, ZERO);
vector<frac> GWP(n, ZERO);
for(int j=0; j<n; j++) {
GWP[j] = frac(game_points[j], 3*tot_game_points[j]);
MWP[j] = frac(match_points[j], tot_match_points*3);
}
for(int j=0; j<n; j++) {
cout<<match_points[j]<<" ";
// auto f1 = match_win_total[j].get_div(tot_matches_played[j]);
frac f1 = ZERO;
for(int i:opponents_played[j]) f1 = adding(f1, MWP[i]);
f1 = f1.get_div(opponents_played[j].size());
auto f2 = GWP[j];
frac f3 = ZERO;
for(int i:opponents_played[j]) f3 = adding(f3, GWP[i]);
f3 = f3.get_div(opponents_played[j].size());
// auto f3 = game_win_total[j].get_div(tot_matches_played[j]);
f1.display();
f2.display();
f3.display();
cout<<"\n";
}
}
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
input:
2 2 3 0 1 1 1 2 2 0 1 1 2 1 1 1 3 2 1 1 1 2 0 2 0 2 3 2 0 0
output:
Round 1 3 1/3 1/1 1/3 3 1/3 1/1 1/3 Round 2 6 1/2 13/15 7/15 3 1/1 7/15 13/15 Round 3 7 4/9 17/24 11/24 4 7/9 11/24 17/24 Round 1 0 1/1 1/3 1/1 3 1/3 1/1 1/3 3 1/3 1/1 1/3 Round 2 3 1/1 1/2 1/1 6 1/2 1/1 1/2 3 1/1 1/2 1/1
result:
ok 17 lines
Test #2:
score: 0
Accepted
time: 175ms
memory: 3576kb
input:
3215 26 4 13 13 11 13 19 9 2 1 0 17 1 0 2 0 25 15 2 0 0 14 5 1 2 0 20 2 0 2 0 10 21 2 1 0 3 16 0 2 0 8 6 2 1 0 26 24 1 2 0 22 18 0 1 2 7 11 2 0 0 13 4 1 2 0 23 12 0 2 0 18 20 1 2 0 3 5 2 1 0 25 24 1 2 0 7 9 1 2 0 11 14 2 0 0 8 17 1 1 1 23 12 2 0 0 19 26 1 2 0 2 15 0 2 0 4 13 2 1 0 16 10 0 2 0 6 21 0...
output:
Round 1 3 1/3 1/1 1/3 3 1/3 1/1 1/3 0 1/1 1/3 1/1 3 1/3 2/3 1/3 3 1/3 2/3 1/3 0 1/1 1/3 2/3 3 1/3 1/1 1/3 3 1/3 2/3 1/3 0 1/1 1/3 2/3 3 1/3 2/3 1/3 0 1/1 1/3 1/1 3 1/3 1/1 1/3 0 1/1 1/3 2/3 0 1/1 1/3 2/3 0 1/1 1/3 1/1 3 1/3 1/1 1/3 0 1/1 1/3 1/1 3 1/3 5/9 1/3 3 1/3 2/3 1/3 0 1/1 1...
result:
ok 312175 lines
Test #3:
score: 0
Accepted
time: 144ms
memory: 3700kb
input:
602 67 7 7 9 4 9 10 6 10 18 36 2 0 0 14 63 1 2 0 20 2 2 1 0 45 17 1 1 1 16 24 0 2 0 15 12 1 1 1 59 38 1 2 0 25 3 1 2 0 19 6 0 2 0 26 51 0 2 0 50 66 1 1 1 4 27 1 2 0 12 5 0 1 2 41 2 1 1 1 54 1 1 1 1 28 29 0 2 0 38 64 1 1 1 46 63 1 1 1 25 44 2 1 0 30 11 0 2 0 60 38 2 0 0 11 39 1 1 1 23 8 1 1 1 2 29 0 ...
output:
Round 1 3 1/3 1/1 1/3 0 1/1 1/3 2/3 3 1/3 1/1 1/3 3 1/3 1/1 1/3 3 1/3 1/1 1/3 3 1/3 1/1 1/3 3 1/3 1/1 1/3 3 1/3 1/1 1/3 3 1/3 1/1 1/3 3 1/3 1/1 1/3 3 1/3 1/1 1/3 1 1/3 4/9 4/9 3 1/3 1/1 1/3 0 1/1 1/3 2/3 1 1/3 4/9 4/9 0 1/1 1/3 1/1 1 1/3 4/9 4/9 3 1/3 1/1 1/3 3 1/3 1/1 1/3 3 1/3 2...
result:
ok 303032 lines
Test #4:
score: 0
Accepted
time: 444ms
memory: 4064kb
input:
36 818 12 399 400 403 401 400 400 399 402 402 403 399 402 484 426 2 1 0 304 580 0 2 0 261 281 2 0 0 739 204 2 0 0 53 297 1 2 0 430 258 2 1 0 521 763 1 2 0 718 526 2 0 0 611 247 1 2 0 644 453 0 2 0 283 91 2 1 0 695 223 1 2 0 583 679 2 1 0 538 396 1 1 1 582 766 1 2 0 146 136 1 2 0 799 77 1 2 0 530 787...
output:
Round 1 0 1/1 1/3 1/1 3 1/3 1/1 1/3 0 1/1 1/3 1/1 3 1/3 2/3 1/3 3 1/3 1/1 1/3 0 1/1 1/3 1/1 3 1/3 2/3 1/3 3 1/3 2/3 1/3 3 1/3 2/3 1/3 0 1/1 1/3 7/9 0 1/1 1/3 1/1 3 1/3 1/1 1/3 0 1/1 1/3 1/1 0 1/1 1/3 1/1 3 1/3 2/3 1/3 0 1/1 1/3 2/3 0 1/1 1/3 2/3 3 1/3 2/3 1/3 0 1/1 1/3 2/3 0 1/1 1...
result:
ok 300314 lines
Test #5:
score: 0
Accepted
time: 430ms
memory: 3732kb
input:
37 986 7 493 493 493 493 493 493 493 753 944 2 1 0 590 186 1 2 0 142 847 2 0 0 11 725 1 2 0 41 445 0 2 0 509 418 1 2 0 500 663 2 0 0 895 401 1 2 0 932 24 0 2 0 14 446 2 0 0 984 170 1 2 0 803 316 0 2 0 36 690 0 2 0 228 719 1 2 0 378 979 2 0 0 650 477 2 0 0 821 496 0 2 0 828 181 1 2 0 303 978 2 0 0 34...
output:
Round 1 3 1/3 7/9 1/3 0 1/1 1/3 1/1 3 1/3 1/1 1/3 3 1/3 1/1 1/3 3 1/3 1/1 1/3 3 1/3 7/9 1/3 1 1/3 4/9 4/9 3 1/3 2/3 1/3 3 1/3 1/1 1/3 3 1/3 2/3 1/3 0 1/1 1/3 2/3 0 1/1 1/3 1/1 3 1/3 1/1 1/3 3 1/3 1/1 1/3 0 1/1 1/3 2/3 3 1/3 2/3 1/3 3 1/3 1/1 1/3 0 1/1 1/3 2/3 0 1/1 1/3 1/1 3 1/3 2...
result:
ok 300065 lines
Test #6:
score: 0
Accepted
time: 407ms
memory: 3744kb
input:
39 455 12 194 198 198 192 188 196 194 193 185 192 193 185 274 152 2 0 0 172 313 2 1 0 324 382 2 0 0 423 41 1 2 0 108 273 2 0 0 88 436 0 2 0 1 386 2 0 0 162 384 2 0 0 176 195 1 1 1 371 303 0 2 0 292 198 0 2 1 98 403 0 2 0 57 225 1 2 0 142 256 1 1 1 362 211 1 1 1 318 265 0 2 0 235 322 2 1 0 126 165 2 ...
output:
Round 1 3 1/3 1/1 1/3 3 1/3 1/1 1/3 0 1/1 1/3 1/1 3 1/3 2/3 1/3 0 1/1 1/3 1/1 3 1/3 1/1 1/3 0 1/1 1/3 2/3 3 1/3 1/1 1/3 3 1/3 1/1 1/3 3 1/3 7/9 1/3 0 1/1 1/3 1/1 3 1/3 2/3 1/3 3 1/3 2/3 1/3 3 1/3 1/1 1/3 3 1/3 1/1 1/3 3 1/3 1/1 1/3 3 1/3 1/1 1/3 0 1/1 1/3 2/3 3 1/3 1/1 1/3 0 1/1 1...
result:
ok 300060 lines
Test #7:
score: 0
Accepted
time: 244ms
memory: 3644kb
input:
1053 46 7 23 23 23 23 23 23 23 46 26 2 1 0 9 14 0 2 0 2 15 2 0 0 12 16 2 0 0 22 29 0 2 0 7 17 2 0 0 20 3 0 2 0 41 31 1 1 1 44 6 0 2 0 32 8 1 1 1 23 36 2 0 0 30 5 1 2 0 4 21 0 2 0 42 34 0 2 0 37 27 1 2 0 19 13 2 1 0 18 38 1 2 0 43 28 2 0 0 24 11 2 1 0 39 10 2 1 0 25 33 0 2 0 35 45 0 2 1 40 1 2 0 0 16...
output:
Round 1 0 1/1 1/3 1/1 3 1/3 1/1 1/3 3 1/3 1/1 1/3 0 1/1 1/3 1/1 3 1/3 2/3 1/3 3 1/3 1/1 1/3 3 1/3 1/1 1/3 1 1/3 4/9 4/9 0 1/1 1/3 1/1 0 1/1 1/3 2/3 0 1/1 1/3 2/3 3 1/3 1/1 1/3 0 1/1 1/3 2/3 3 1/3 1/1 1/3 0 1/1 1/3 1/1 0 1/1 1/3 1/1 0 1/1 1/3 1/1 0 1/1 1/3 2/3 3 1/3 2/3 1/3 0 1/1 1...
result:
ok 306093 lines
Test #8:
score: 0
Accepted
time: 416ms
memory: 4068kb
input:
38 408 9 202 201 202 202 201 199 203 201 202 145 197 0 2 0 303 110 2 1 0 168 83 1 2 0 312 254 2 1 0 120 27 0 2 0 162 194 0 2 0 133 128 1 2 0 146 268 2 1 0 238 52 2 0 0 147 72 0 2 0 280 95 2 1 0 211 322 1 2 0 118 400 2 1 0 138 123 2 0 0 101 328 0 2 0 172 267 2 0 0 293 313 1 2 0 360 189 2 1 0 193 202 ...
output:
Round 1 3 1/3 2/3 1/3 3 1/3 1/1 1/3 0 1/1 1/3 1/1 3 1/3 1/1 1/3 3 1/3 1/1 1/3 3 1/3 2/3 1/3 3 1/3 1/1 1/3 0 1/1 1/3 2/3 3 1/3 1/1 1/3 0 1/1 1/3 2/3 3 1/3 1/1 1/3 3 1/3 1/1 1/3 0 1/1 1/3 2/3 3 1/3 1/1 1/3 3 1/3 1/1 1/3 3 1/3 2/3 1/3 0 1/1 1/3 2/3 3 1/3 1/1 1/3 3 1/3 2/3 1/3 0 1/1 1...
result:
ok 299664 lines
Test #9:
score: 0
Accepted
time: 459ms
memory: 3820kb
input:
34 682 11 336 339 338 337 338 339 338 335 338 336 334 75 474 2 0 0 368 334 2 0 0 501 600 0 2 0 133 291 0 2 0 630 498 0 2 0 125 681 1 2 0 393 198 1 2 0 17 574 0 2 0 558 217 2 1 0 121 71 2 1 0 355 188 2 0 0 598 351 2 0 0 80 593 0 2 1 540 508 0 2 0 647 63 2 1 0 287 447 0 2 0 409 141 0 2 0 543 459 1 2 0...
output:
Round 1 3 1/3 2/3 1/3 0 1/1 1/3 1/1 3 1/3 2/3 1/3 3 1/3 2/3 1/3 3 1/3 1/1 1/3 1 1/3 4/9 4/9 3 1/3 1/1 1/3 0 1/1 1/3 1/1 3 1/3 2/3 1/3 0 1/1 1/3 1/1 0 1/1 1/3 2/3 0 1/1 1/3 1/1 0 1/1 1/3 2/3 3 1/3 7/9 1/3 3 1/3 2/3 1/3 3 1/3 1/1 1/3 0 1/1 1/3 1/1 0 1/1 1/3 2/3 3 1/3 2/3 1/3 3 1/3 2...
result:
ok 299852 lines
Test #10:
score: -100
Wrong Answer
time: 458ms
memory: 3772kb
input:
18 1000 16 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 906 272 2 0 1 150 792 2 1 0 499 344 0 0 3 809 137 2 1 0 321 309 2 0 1 606 363 2 1 0 62 813 2 0 1 63 354 1 1 1 530 921 1 0 2 325 532 1 1 1 830 439 2 0 1 558 735 1 1 1 157 106 2 0 0 915 166 2 1 0 990 528 0 2 1 503 833 2 0 0 221...
output:
Round 1 0 1/1 1/3 7/9 0 1/1 1/3 5/9 0 1/1 1/3 1/1 0 1/1 1/3 7/9 1 1/3 4/9 4/9 1 1/3 1/3 1/3 1 1/3 1/3 1/3 3 1/3 1/1 1/3 1 1/3 4/9 4/9 3 1/3 5/9 1/3 3 1/3 1/1 1/3 3 1/3 7/9 1/3 3 1/3 5/9 1/3 3 1/3 2/3 1/3 0 1/1 1/3 2/3 0 1/1 1/3 5/9 1 1/3 4/9 4/9 3 1/3 2/3 1/3 3 1/3 1/1 1/3 3 1/3 7...
result:
wrong answer 15254th lines differ - expected: '19 127/256 16/39 190076978945855279/393967202192403840', found: '19 127/256 16/39 1/3 '