QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#324015#4829. Mark on a Graphhotboy27030 40ms12236kbC++141.9kb2024-02-10 15:13:132024-02-10 15:13:13

Judging History

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

  • [2024-02-10 15:13:13]
  • 评测
  • 测评结果:0
  • 用时:40ms
  • 内存:12236kb
  • [2024-02-10 15:13:13]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
mt19937_64 rng(1);
ll random(ll l,ll r){
    return rng()%(r-l+1)+l;
}
ll myrandom(ll i){
    return rng()%i;
}
ll n,m;
ll val[1010][1010];
struct graph{
    set <pll> s;
    void add_edge(ll u,ll v){
        if (u > v)swap(u,v);
        if (s.find({u,v})==s.end())s.insert({u,v});
        else s.erase({u,v});
    }
    ll cnt[1010];
    ll eval(){
        memset(cnt,0,sizeof cnt);
        for (auto x:s)cnt[x.fi]++,cnt[x.se]++;
        ll res = 0;
        for (auto x:s){
            res ^= val[cnt[x.fi]][cnt[x.fi]];
        }
        return res;
    }
};
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    for (ll i = 1;i <= 1000;i ++){
        for (ll j = 1;j <= 1000;j ++){
            val[i][j] = random(0,1023);
        }
    }
    cin>>n>>m;
    graph g;
    for (ll i = 1;i <= m;i ++){
        ll u,v;
        cin>>u>>v;
        g.add_edge(u,v);
    }
    if (g.eval() == 69){
        cout<<"ok"<<endl;
    }
    else{
        cout<<"mark"<<endl;
        vector <pll> ans;
        while (1){
            vector <pll> cur;

            for (ll i = 0;i < 5;i++){
                ll u,v;
                u = random(1,n),v = random(1,n);
                while (u==v)u = random(1,n),v = random(1,n);
                cur.push_back({u,v});
            }
            graph tmp = g;
            for (auto x:cur){
                tmp.add_edge(x.fi,x.se);
            }
            if (tmp.eval()==69){
                ans = cur;
                break;
            }
        }
        cout<<sz(ans)<<'\n';
        for (auto x:ans)cout<<x.fi<<' '<<x.se<<'\n';;
    }
//    cout<<even<<'\n';
}


詳細信息

Test #1:

score: 0
Wrong Answer
time: 40ms
memory: 12236kb

input:

1000 3560
603 151
415 20
102 569
895 552
678 734
24 614
689 518
440 223
751 919
223 433
711 551
502 634
706 583
812 501
514 535
780 751
720 530
532 384
888 139
864 791
292 675
171 881
30 592
464 557
280 299
654 650
894 335
250 532
792 10
83 969
118 771
579 300
852 983
243 940
957 939
817 889
911 319...

output:

mark
5
914 932
453 759
462 120
269 370
553 559

input:

1000 3565
626 311
295 222
665 298
534 977
682 582
107 833
155 683
656 841
184 255
392 381
676 187
63 633
397 161
770 790
655 180
484 763
439 897
224 648
974 380
521 228
368 520
676 977
113 49
66 583
715 526
457 125
567 806
70 757
464 840
87 733
355 335
232 412
14 201
368 394
201 178
992 583
557 937
...

output:

mark
5
260 515
298 73
757 175
753 34
827 999

result:

wrong answer Token "mark" doesn't correspond to pattern "ok"