QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#334601 | #5423. Perfect Matching | yllcm | WA | 300ms | 19196kb | C++14 | 1.7kb | 2024-02-22 08:40:23 | 2024-02-22 08:40:24 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define FR first
#define SE second
using namespace std;
inline int read() {
int x = 0; bool op = false;
char c = getchar();
while(!isdigit(c))op |= (c == '-'), c = getchar();
while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return op ? -x : x;
}
const int N = 2e5 + 10;
int n;
int a[N], vis[N], vm[N];
vector<pii> G[N];
vector<pii> mat;
void dfs(int u, int fid) {
vector<int> V;
for(auto t : G[u]) {
int id = t.FR, v = t.SE;
if(vis[v]) {if(!vm[id] && id != fid)V.pb(id); continue;}
vis[v] = true; dfs(v, id);
if(vm[id] == false)V.pb(id);
}
if((V.size() & 1) && fid)V.pb(fid);
for(int i = 0; i + 1 < V.size(); i += 2)
vm[V[i]] = vm[V[i + 1]] = true, mat.pb({V[i], V[i + 1]});
return ;
}
void solve() {
n = read();
for(int i = 1; i <= n; i++)a[i] = read();
map<int, int> id; int tot = 0;
for(int i = 1; i <= n; i++) {
if(!id.count(i + a[i]))id[i + a[i]] = ++tot;
if(!id.count(i - a[i]))id[i - a[i]] = ++tot;
G[id[i + a[i]]].pb({i, id[i - a[i]]});
G[id[i - a[i]]].pb({i, id[i + a[i]]});
}
vector<pii>().swap(mat);
for(int i = 1; i <= tot; i++)if(!vis[i])vis[i] = true, dfs(i, 0);
for(int i = 1; i <= tot; i++) {
vector<pii>().swap(G[i]);
vis[i] = false;
}
for(int i = 1; i <= n; i++)vm[i] = false;
if(mat.size() != n / 2)return puts("No"), void();
puts("Yes");
for(auto t : mat)printf("%d %d\n", t.FR, t.SE);
return ;
}
int main() {
int test = read();
while(test--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 9916kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 1 4 5 2 6 3 Yes 1 3 4 2 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 300ms
memory: 19196kb
input:
10 100000 0 -1 -2 -3 -4 -5 -2 -7 -8 -9 -10 -9 -12 13 14 15 -16 -17 -18 19 20 19 -22 -21 -20 -25 -26 -27 -28 -27 -26 31 30 29 -34 -35 -34 39 38 37 42 41 42 47 44 45 46 49 48 -53 -52 -51 -56 -55 -54 55 56 57 -58 -59 -60 61 62 63 64 65 64 67 66 69 70 73 72 73 74 73 76 75 74 79 80 81 -84 -83 -84 89 86 8...
output:
Yes 11 12 21 22 5 7 29 30 32 33 77 78 98 99 122 123 128 129 137 138 200 201 203 205 224 225 242 244 287 289 290 291 308 309 314 315 320 321 335 337 362 364 371 372 377 378 380 382 389 391 395 396 416 417 434 435 449 450 458 459 461 462 479 480 509 511 515 517 518 520 524 526 554 556 566 567 584 586 ...
result:
wrong answer abs(3-31) != abs(a[3]-a[31]) (test case 1)