QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#590645#9347. Competition in Swiss-systemkevinshanWA 466ms3984kbC++234.3kb2024-09-26 09:23:252024-09-26 09:23:26

Judging History

你现在查看的是最新测评结果

  • [2024-09-26 09:23:26]
  • 评测
  • 测评结果:WA
  • 用时:466ms
  • 内存:3984kb
  • [2024-09-26 09:23:25]
  • 提交

answer

#pragma GCC optimize("Ofast,O3,unroll-loops")

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

#define ll unsigned 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() { 
        if(den == 0) return 1;
        if(den / 3 >= num) return 1;
        return 0;
    }
    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";
            }
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 166ms
memory: 3624kb

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: 149ms
memory: 3984kb

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: 429ms
memory: 3828kb

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: 432ms
memory: 3828kb

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: 3788kb

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: 227ms
memory: 3912kb

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: 410ms
memory: 3844kb

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: 448ms
memory: 3844kb

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: 466ms
memory: 3840kb

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 15951st lines differ - expected: '23 419/768 7/15 413935711456329163/787934404384807680', found: '23 419/768 7/15 1/3 '