QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#334601#5423. Perfect MatchingyllcmWA 300ms19196kbC++141.7kb2024-02-22 08:40:232024-02-22 08:40:24

Judging History

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

  • [2024-02-22 08:40:24]
  • 评测
  • 测评结果:WA
  • 用时:300ms
  • 内存:19196kb
  • [2024-02-22 08:40:23]
  • 提交

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)