QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#115373#5423. Perfect MatchingGeothermal#AC ✓1026ms22484kbC++173.9kb2023-06-26 04:23:292023-06-26 04:23:29

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-26 04:23:29]
  • 评测
  • 测评结果:AC
  • 用时:1026ms
  • 内存:22484kb
  • [2023-06-26 04:23:29]
  • 提交

answer

#include "bits/stdc++.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif


const int MOD = 1000000007;
const char nl = '\n';
const int MX = 200001; 

vector<vpi> graph;
vector<vi> as;

int vis[MX];

bool dfs(int v, int p, int pe) {
    vis[v] = 1;
    trav(a, graph[v]) {
        if (vis[a.f] == 2) continue;
        if (vis[a.f] == 1) {
            if (a.s != pe) as[v].pb(a.s); 
            continue;
        }
        if (!dfs(a.f, v, a.s)) return false;
    }
    if (sz(as[v]) % 2) {
        if (p == -1) return false;
        as[v].pb(pe);
    } else if (p != -1) {
        as[p].pb(pe);
    }
    vis[v] = 2;
    return true;
}

void solve() {
    int N; cin >> N;
    graph.clear();
    map<int, int> m1, m2;
    int nxt = 0;
    F0R(i, N) {
        int X; cin >> X;
        if (!m1.count(i+X)) {
            m1[i+X] = nxt; nxt++;
            graph.pb(vpi());
        }
        if (!m2.count(X-i)) {
            m2[X-i] = nxt; nxt++;
            graph.pb(vpi());
        }
        graph[m1[i+X]].pb({m2[X-i], i+1});
        graph[m2[X-i]].pb({m1[i+X], i+1});
    }
    as = vector<vi>(sz(graph));
    F0R(i, sz(graph)) vis[i] = 0;
    F0R(i, sz(graph)) {
        if (vis[i] == 2) continue;
        if (!dfs(i, -1, -1)) {
            cout << "No" << nl; return;
        }
    }

    //dbg(as);
    cout << "Yes" << nl;
    F0R(i, sz(graph)) {
        F0R(j, sz(as[i]) / 2) {
            cout << as[i][j*2] << " " << as[i][j*2+1] << nl; 
        }
    }

}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int T = 1;
    cin >> T;
    while(T--) {
        solve();
    }

	return 0;
}



Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3496kb

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: 0
Accepted
time: 376ms
memory: 17020kb

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
1 4
6 8
9 10
13 17
18 19
26 27
28 35
59 60
61 85
89 92
108 110
111 112
113 114
115 119
125 131
132 133
134 135
136 143
144 145
153 161
181 186
194 199
204 212
217 218
219 220
221 222
223 230
231 232
234 271
296 297
298 305
306 307
326 329
334 338
341 342
343 347
350 359
360 361
363 390
411 415
4...

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 1ms
memory: 3524kb

input:

10
100
28761184 28761185 28761186 28761187 28761188 28761189 28761190 28761191 -20675012 -20675013 -20675014 -20675015 -20675016 -20675017 -20675018 -20675019 -20675020 -20675021 -20675022 -20675023 -20675024 -20675025 -20675026 -20675027 -20675028 -20675029 -20675030 -20675031 -36758138 -36758139 -...

output:

Yes
2 3
4 5
6 7
8 1
9 10
11 12
13 14
15 16
17 18
19 20
21 22
23 24
25 26
27 28
29 30
31 32
33 34
36 37
38 35
40 41
42 43
44 45
46 47
48 49
50 51
52 53
54 55
56 57
58 39
59 60
61 62
63 64
65 66
67 68
69 70
71 72
73 74
75 76
77 78
79 80
81 82
83 84
85 86
87 88
89 90
91 92
93 94
95 96
97 98
99 100
Yes
...

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 409ms
memory: 22484kb

input:

10
100000
-40608960 -40608959 -40608958 -40608957 -40608956 -40608955 -40608954 -40608953 -40608952 -40608951 -40608950 -40608949 -40608948 -40608947 -40608946 -40608945 -40608944 -40608943 -40608942 -40608941 -40608940 -40608939 -40608938 -40608937 -40608936 -40608935 -40608934 -40608933 -40608932 ...

output:

Yes
2 3
4 5
6 7
8 9
10 11
12 13
14 15
16 17
18 19
20 21
22 23
24 25
26 27
28 29
30 31
32 33
34 35
36 37
38 39
40 41
42 43
44 45
46 47
48 49
50 51
52 53
54 55
56 57
58 59
60 61
62 63
64 65
66 67
68 69
70 71
72 73
74 75
76 77
78 79
80 81
82 83
84 85
86 87
88 89
90 91
92 93
94 95
96 97
98 99
100 101
10...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 1026ms
memory: 19404kb

input:

10
100000
0 -1 -2 3 2 5 6 7 -2 1 0 9 12 11 -8 13 8 -7 16 17 -10 19 22 21 22 23 4 -15 -18 -17 -6 -31 -14 25 32 -25 26 27 -32 31 38 -31 -32 -19 -30 -35 46 45 -48 -37 48 41 46 -43 -44 53 56 55 50 -27 52 61 62 -33 -18 19 64 45 46 -57 -8 -25 -26 -11 -22 49 -66 -65 -66 29 78 -15 74 83 12 83 14 85 86 -7 -5...

output:

Yes
1 1932
1986 3820
8799 9282
9393 9892
13027 13900
17031 20491
20817 22113
31175 32797
34960 39303
45082 59024
61232 71444
76524 76759
78974 79799
80672 84250
93166 98041
99492 99604
4 4547
5575 9434
10099 12181
13774 15891
16010 18788
18971 22179
25998 26530
27228 28244
28379 31832
33584 34334
37...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 262ms
memory: 3740kb

input:

1000
1000
-2 0 3 4 6 7 4 7 6 9 11 9 10 12 16 13 16 17 18 20 19 19 24 22 25 23 28 25 26 27 30 32 31 34 36 37 34 37 37 40 42 43 44 45 43 44 46 45 50 48 51 49 54 55 52 55 54 57 56 61 60 61 64 65 64 67 65 66 67 68 71 73 73 75 76 77 78 75 76 78 82 79 80 81 83 83 87 88 90 89 90 93 92 93 95 94 96 96 100 97...

output:

No
No
No
No
No
No
Yes
4 11
13 30
39 40
46 50
53 54
58 69
76 88
89 92
94 105
106 114
116 120
123 125
132 133
135 137
138 150
153 163
172 173
181 187
188 194
222 225
227 228
236 242
254 256
275 288
289 291
299 317
352 355
371 389
410 425
434 447
451 469
480 485
491 492
494 506
508 509
511 512
516 521
...

result:

ok 1000 Cases (1000 test cases)