QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#115373 | #5423. Perfect Matching | Geothermal# | AC ✓ | 1026ms | 22484kb | C++17 | 3.9kb | 2023-06-26 04:23:29 | 2023-06-26 04:23:29 |
Judging History
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)