QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#324015 | #4829. Mark on a Graph | hotboy2703 | 0 | 40ms | 12236kb | C++14 | 1.9kb | 2024-02-10 15:13:13 | 2024-02-10 15:13:13 |
Judging History
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"