QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#771785 | #5423. Perfect Matching | juruoA | TL | 0ms | 22556kb | C++14 | 3.9kb | 2024-11-22 15:39:57 | 2024-11-22 15:39:58 |
Judging History
answer
#include <bits/stdc++.h>
using std::bitset;
using std::cout;
using std::deque;
using std::endl;
using std::greater;
using std::lower_bound;
using std::make_pair;
using std::map;
using std::max;
using std::min;
using std::multimap;
using std::multiset;
using std::nth_element;
using std::pair;
using std::priority_queue;
using std::queue;
using std::reverse;
using std::set;
using std::sort;
using std::sqrt;
using std::stable_sort;
using std::string;
using std::swap;
using std::unique;
using std::upper_bound;
using std::vector;
typedef int li;
typedef long double lf;
inline li read(){
li ans = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
f = (ch == '-') ? -1 : 1;
ch = getchar();
}
while(ch <= '9' && ch >= '0'){
ans = ans * 10 + (ch ^ 48);
ch = getchar();
}
return ans * f;
}
std::unordered_map<li, li> id, id2;
li lenp, n, a[2000010], lenp2;
li getid(li x){
if(!id[x]) id[x] = ++lenp;
return id[x];
}
li getid2(li x){
if(!id2[x]) id2[x] = ++lenp2;
return id2[x];
}
li cnt[2000010], fl;
vector<li> v[200010];
set<li> v2[200010];
vector<pair<li, li>> ans;
li vis[200010];
li belong[200010], belong2[200010];
li abss(li x){
return x > 0 ? x : -x;
}
vector<li> V;
int main(){
// freopen("wonderful.ans", "r", stdin);
// freopen("www.ww", "w", stdout);
// freopen("matching.in", "r", stdin);
// freopen("matching.out", "w", stdout);
li T = read();
while(T--){
lenp = 0, lenp2 = 0;
li type = 1;
id.clear(), id2.clear();
n = read();
for(li i = 1; i <= n; i++){
a[i] = read();
type &= (i == 1 || a[i] >= a[i - 1]);
cnt[i] = 0;
v[i].clear(), v2[i].clear();
}
for(li i = 1; i <= n; i++){
li x = getid(i - a[i]);
cnt[x]++;
v[x].push_back(i);
belong[i] = x;
}
for(li i = 1; i <= n; i++){
li x = getid2(i + a[i]);
v2[x].insert(i);
belong2[i] = x;
}
ans.clear();
memset(vis, 0, sizeof vis);
fl = 1;
li tot = 0;
for(li i = 1; i <= lenp; i++){
if(cnt[i] & 1) tot++;
}
for(li i = 1; i <= lenp && fl; i++){
li old = tot;
if(cnt[i] % 2 == 0) continue;
li xx = 1;
for(li j : v[i]){
if(vis[j]) continue;
if(!xx) break;
li pos = getid2(j + a[j]);
V.clear();
for(li s : v2[pos]){
if(vis[s] || cnt[belong[s]] % 2 == 0 || s == j){
V.push_back(s);
} else{
xx = 0;
cnt[i]--, cnt[belong[s]]--;
vis[j] = vis[s] = 1;
V.push_back(j), V.push_back(s);
ans.push_back({j, s});
tot -= 2;
break;
}
}
for(li x : V){
v2[j].erase(x);
}
}
if(tot == old){
fl = 0;
}
}
if(fl){
for(li i = 1; i <= lenp; i++){
V.clear();
for(li u : v[i]){
if(!vis[u]) V.push_back(u);
}
for(li i = 0; i < V.size(); i += 2){
ans.push_back({V[i], V[i + 1]});
}
}
}
if(fl){
printf("Yes\n");
assert(n / 2 == ans.size());
for(auto x : ans){
printf("%d %d\n", x.first, x.second);
}
} else{
printf("No\n");
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 22556kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 1 4 2 5 3 6 Yes 1 3 2 4 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: -100
Time Limit Exceeded
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...