QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#334598#5423. Perfect MatchingyllcmWA 294ms32248kbC++141.6kb2024-02-22 08:35:432024-02-22 08:35:43

Judging History

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

  • [2024-02-22 08:35:43]
  • 评测
  • 测评结果:WA
  • 用时:294ms
  • 内存:32248kb
  • [2024-02-22 08:35:43]
  • 提交

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])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 < 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);
  if(mat.size() != n / 2)return puts("No"), void();
  puts("Yes");
  for(auto t : mat)printf("%d %d\n", t.FR, t.SE);
  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;
  return ;
}
int main() {
  int test = read();
  while(test--)solve();
  return 0;
}

详细

Test #1:

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

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: 294ms
memory: 32248kb

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:

No
No
No
No
No
No
No
No
No
No

result:

wrong answer std outputs a valid answer while participant doesn't (test case 1)