QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#771785#5423. Perfect MatchingjuruoATL 0ms22556kbC++143.9kb2024-11-22 15:39:572024-11-22 15:39:58

Judging History

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

  • [2024-11-22 15:39:58]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:22556kb
  • [2024-11-22 15:39:57]
  • 提交

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...

output:


result: