QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#405529#7861. Inverse Topological Sortdnialh#AC ✓180ms31988kbC++206.7kb2024-05-06 04:42:142024-11-22 19:54:43

Judging History

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

  • [2024-11-22 19:54:43]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:180ms
  • 内存:31988kb
  • [2024-11-22 19:52:53]
  • hack成功,自动添加数据
  • (/hack/1241)
  • [2024-05-06 04:42:14]
  • 评测
  • 测评结果:100
  • 用时:187ms
  • 内存:31876kb
  • [2024-05-06 04:42:14]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define F0R(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i <= b; i++)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define FORd(i,a,b) for (int i = (b); i >= (a); i--)
#define trav(a, x) for (auto& a : x)
#define rep(i, a, b) for(int i = a; i < (b); ++i)

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

const char nl = '\n';
const int MAX_N = 100011;
const ll INF = (1<<29) + 123;
const ll MOD = 1000000007; // 998244353
const ld PI = 4*atan((ld)1);

template <typename T> bool ckmin(T& a, const T& b) { return a > b ? a=b, 1 : 0; }
template <typename T> bool ckmax(T& a, const T& b) { return b > a ? a=b, 1 : 0; }

/**** Credit to chatgpt 4.0 ****/

// Stream operator for std::pair
template<typename T1, typename T2>
ostream& operator<<(ostream &out, const pair<T1, T2> &v) {
    out << "(" << v.first << ", " << v.second << ")"; 
    return out;
}

// Trait to check if a type is iterable
template<typename T, typename = void>
struct is_iterable : false_type {};

template<typename T>
struct is_iterable<T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>()))>> : true_type {};

// Stream operator for iterable types excluding std::string
template<typename TT>
typename enable_if<is_iterable<TT>::value && !is_same<TT, string>::value, ostream&>::type
operator<<(ostream& out, const TT& c) {
    out << "{ ";
    for (const auto& x : c) out << x << " ";
    out << "}"; 
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, std::stack<T> container) {
    std::vector<T> elements;
    while (!container.empty()) {
        elements.push_back(container.top());
        container.pop();
    }
    std::reverse(elements.begin(), elements.end()); // Reverse to maintain order
    return out << elements;
}

template<typename T>
ostream& operator<<(ostream& out, std::queue<T> container) {
    std::vector<T> elements;
    while (!container.empty()) {
        elements.push_back(container.front());
        container.pop();
    }
    return out << elements;
}

// Helper function to print std::priority_queue
template<typename T, typename Container, typename Compare>
ostream& operator<<(ostream& out, std::priority_queue<T, Container, Compare> pq) {
    out << "{";
    while (!pq.empty()) {
        out << " " << pq.top();
        pq.pop();
    }
    out << " }";
    return out;
}

#ifdef DBG
void dbg_out() { cerr << endl; }

template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
    cerr << ' ' << H;
    dbg_out(T...);
}

#define dbg(...) cerr << #__VA_ARGS__ << ":", dbg_out(__VA_ARGS__);
#define dbg_array(a, n) cerr << #a << ": { "; for(int i = 0; i < n; i++) cerr << a[i] << " "; cerr << "}\n";
#else
#define dbg(...)
#define dbg_array(a, n)
#endif

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MX = 3e5+5;

const int inf = 1e9;
struct Node {
	Node *l = 0, *r = 0;
	int lo, hi, mset = inf, madd = 0, val = -inf;
	Node(int lo,int hi):lo(lo),hi(hi){} // Large interval of -inf
	Node(vi& v, int lo, int hi) : lo(lo), hi(hi) {
		if (lo + 1 < hi) {
			int mid = lo + (hi - lo)/2;
			l = new Node(v, lo, mid); r = new Node(v, mid, hi);
			val = max(l->val, r->val);
		}
		else val = v[lo];
	}
	int query(int L, int R) {
		if (R <= lo || hi <= L) return -inf;
		if (L <= lo && hi <= R) return val;
		push();
		return max(l->query(L, R), r->query(L, R));
	}
	void set(int L, int R, int x) {
		if (R <= lo || hi <= L) return;
		if (L <= lo && hi <= R) mset = val = x, madd = 0;
		else {
			push(), l->set(L, R, x), r->set(L, R, x);
			val = max(l->val, r->val);
		}
	}
	void add(int L, int R, int x) {
		if (R <= lo || hi <= L) return;
		if (L <= lo && hi <= R) {
			if (mset != inf) mset += x;
			else madd += x;
			val += x;
		}
		else {
			push(), l->add(L, R, x), r->add(L, R, x);
			val = max(l->val, r->val);
		}
	}
	void push() {
		if (!l) {
			int mid = lo + (hi - lo)/2;
			l = new Node(lo, mid); r = new Node(mid, hi);
		}
		if (mset != inf)
			l->set(lo,hi,mset), r->set(lo,hi,mset), mset = inf;
		else if (madd)
			l->add(lo,hi,madd), r->add(lo,hi,madd), madd = 0;
	}
};

vi topoSortMin(const vector<vi>& gr) {
	vi indeg(sz(gr)), ret;
	for (auto& li : gr) for (int x : li) indeg[x]++;
	priority_queue<int, vi, greater<int>> q; // use priority_queue for lexic. largest ans.
	rep(i,0,sz(gr)) if (indeg[i] == 0) q.push(i);
	while (!q.empty()) {
		int i = q.top(); // top() for priority queue
		ret.push_back(i);
		q.pop();
		for (int x : gr[i])
			if (--indeg[x] == 0) q.push(x);
	}
	return ret;
}

vi topoSortMax(const vector<vi>& gr) {
	vi indeg(sz(gr)), ret;
	for (auto& li : gr) for (int x : li) indeg[x]++;
	priority_queue<int> q; // use priority_queue for lexic. largest ans.
	rep(i,0,sz(gr)) if (indeg[i] == 0) q.push(i);
	while (!q.empty()) {
		int i = q.top(); // top() for priority queue
		ret.push_back(i);
		q.pop();
		for (int x : gr[i])
			if (--indeg[x] == 0) q.push(x);
	}
	return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vi a(n); F0R(i, n) { cin >> a[i]; a[i]--; }
    vi b(n); F0R(i, n) { cin >> b[i]; b[i]--; }
    int posA[n]; F0R(i, n) posA[a[i]] = i;
    int posB[n]; F0R(i, n) posB[b[i]] = i;
    Node st(0, n);
    vector<vi> gr(n);
    int ans = 0;
    F0R(i, n) {
        int v = st.query(0, posB[a[i]]);
        if (v != -inf) {
            ans++;
            gr[a[v]].pb(a[i]);
            dbg(a[v], a[i]);
        }
        st.set(posB[a[i]], posB[a[i]]+1, i);
    }
    Node st1(0, n);
    F0R(i, n) {
        int v = st1.query(0, posA[b[i]]);
        if (v != -inf) {
            ans++;
            gr[b[v]].pb(b[i]);
            dbg(b[v], b[i]);
        }
        st1.set(posA[b[i]], posA[b[i]]+1, i);
    }
    vi A = topoSortMin(gr);
    vi B = topoSortMax(gr);
    dbg(A, B);
    if (a == A && b == B) {
        cout << "Yes" << endl;
        vpi ans;
        F0R(i, n) {
            // dedup
            set<int> s;
            trav(x, gr[i]) s.insert(x);
            trav(x, s) ans.pb({i, x});
        }
        cout << sz(ans) << endl;
        trav(p, ans) cout << p.f+1 << ' ' << p.s+1 << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

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

input:

3
1 2 3
1 2 3

output:

Yes
2
1 2
2 3

result:

ok n=3

Test #2:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

3
1 2 3
3 2 1

output:

Yes
0

result:

ok n=3

Test #3:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

3
3 2 1
1 2 3

output:

No

result:

ok n=3

Test #4:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

10
6 8 9 4 1 3 7 5 10 2
8 6 9 10 4 7 5 3 2 1

output:

Yes
10
3 2
4 1
4 3
4 7
6 9
7 5
8 9
9 4
9 10
10 2

result:

ok n=10

Test #5:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

10
4 2 5 6 7 8 9 1 3 10
8 7 9 6 5 4 2 1 10 3

output:

Yes
7
1 3
1 10
2 1
4 2
7 9
8 9
9 1

result:

ok n=10

Test #6:

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

input:

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

output:

Yes
156
1 41
2 40
2 86
3 78
3 91
4 47
4 61
4 80
5 2
5 4
7 81
7 96
8 94
9 32
10 77
11 4
11 54
11 93
12 6
12 9
12 11
12 40
13 8
14 74
14 79
15 8
15 72
15 95
16 12
16 71
18 77
19 44
19 63
19 67
20 1
20 59
23 29
23 56
24 69
25 23
25 75
26 28
27 90
31 12
32 45
32 61
32 80
32 97
35 19
35 55
35 73
36 28
36...

result:

ok n=100

Test #7:

score: 0
Accepted
time: 0ms
memory: 3968kb

input:

1000
11 2 29 50 53 54 155 162 211 213 223 240 270 226 243 276 288 304 315 341 249 358 359 381 178 402 51 417 434 163 459 466 471 498 327 464 518 527 549 559 113 581 589 60 347 594 504 593 598 603 607 610 619 648 649 658 681 684 416 686 153 712 575 741 349 382 759 322 17 289 763 764 774 718 777 9 637...

output:

Yes
1682
1 964
2 598
2 901
3 229
3 823
5 129
5 255
5 323
5 685
5 957
6 487
7 551
7 989
8 476
9 203
11 2
11 549
12 335
12 975
13 12
14 190
14 234
15 10
16 93
16 650
17 366
18 8
18 789
19 669
19 925
19 955
20 45
20 528
20 646
21 7
21 799
21 993
22 268
22 895
23 354
25 24
25 69
25 624
26 115
26 351
26 ...

result:

ok n=1000

Test #8:

score: 0
Accepted
time: 123ms
memory: 30392kb

input:

100000
1 5 10 12 13 14 16 17 18 19 21 27 28 33 37 40 41 44 45 49 50 51 52 54 57 58 62 64 67 69 71 72 74 75 77 78 79 80 84 89 93 95 96 100 102 104 111 113 115 117 118 119 120 121 122 123 124 126 127 129 132 135 136 138 139 142 144 150 151 152 153 154 155 156 164 166 167 170 174 177 178 180 181 182 18...

output:

Yes
105782
1 17591
4 16417
5 2
5 3
5 4
7 6
8 660
9 50540
9 68381
10 52585
12 11
12 56242
12 72683
13 88560
16 15
16 79923
17 67167
18 65533
21 20
23 39356
23 88336
24 23
26 24
26 25
27 22
27 26
28 89241
29 25359
32 74286
33 32
35 34
37 35
37 36
39 38
39 76038
40 39
40 99843
43 16914
44 10571
44 4906...

result:

ok n=100000

Test #9:

score: 0
Accepted
time: 180ms
memory: 31960kb

input:

100000
40 84 102 116 124 157 177 191 193 199 256 259 293 300 304 326 430 439 473 477 489 511 515 518 547 583 593 630 664 697 747 751 769 787 789 892 928 945 963 971 978 1052 1063 1067 1077 1080 1088 1101 1136 1143 1172 1180 1198 1274 1312 1359 1361 1380 1382 1404 1414 1428 1435 1466 1475 1497 1517 1...

output:

Yes
172864
1 78240
1 94272
2 59951
3 8556
3 23282
3 44375
3 65454
3 94123
4 1
4 14197
4 63548
4 93492
5 94247
6 4205
6 68727
7 6038
7 35710
7 65396
9 54509
9 75245
9 83190
9 94735
10 8
10 81625
12 46267
12 65431
12 71103
12 94249
12 95137
13 87173
14 18361
14 19116
14 21488
14 24176
14 32742
14 4496...

result:

ok n=100000

Test #10:

score: 0
Accepted
time: 67ms
memory: 28028kb

input:

100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 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 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 102...

output:

Yes
3937
16 15
28 25410
43 29010
44 85590
50 3874
51 75818
161 160
175 174
257 2501
277 276
386 65575
404 403
418 417
456 455
473 5377
526 40026
540 66586
541 540
547 86971
567 23179
568 35479
612 91704
712 45430
714 36371
765 27333
869 11574
882 881
891 890
947 946
971 970
996 42158
1031 80047
1105...

result:

ok n=100000

Test #11:

score: 0
Accepted
time: 155ms
memory: 31616kb

input:

100000
4 6 12 16 20 23 24 27 32 34 36 39 46 54 68 76 77 81 86 88 95 99 103 107 112 113 117 120 125 140 142 143 149 158 161 167 171 174 176 187 190 192 195 198 200 206 207 211 217 222 226 227 231 233 239 240 241 245 247 249 264 274 275 276 277 280 288 290 296 303 305 312 321 329 333 336 338 339 341 3...

output:

Yes
137320
1 15134
1 30430
1 58468
2 47921
2 71317
3 13876
4 1
4 2
4 3
6 5
6 90079
7 20996
7 77815
7 98222
8 59713
8 77674
9 11461
10 77700
11 84060
11 88275
12 8
12 9
12 11
12 54141
12 71044
14 18193
14 65591
14 75438
14 80594
14 91906
14 91948
16 29214
16 88441
18 20804
18 23039
19 1435
19 71741
2...

result:

ok n=100000

Test #12:

score: 0
Accepted
time: 112ms
memory: 29740kb

input:

100000
1 2 4 5 6 7 10 13 14 15 16 20 21 22 24 25 26 28 29 30 31 33 34 35 36 37 38 39 40 43 44 45 46 47 48 51 52 55 56 57 58 59 62 65 66 67 68 69 70 71 72 73 74 75 76 77 78 80 81 82 85 87 89 91 92 93 94 97 98 99 100 101 102 103 104 105 106 107 111 112 113 115 117 119 120 121 123 124 128 130 132 133 1...

output:

Yes
70255
3 71695
4 3
9 8
10 15024
11 12141
12 11
12 98511
13 29204
13 50166
13 72446
13 95895
18 17
18 13280
19 39683
20 18
20 19
24 23
26 47772
28 27
33 18117
35 68646
35 76958
39 63164
42 41
42 61908
43 42
43 57505
43 77968
46 83128
47 97602
48 90140
50 49
51 50
53 1575
54 53
55 54
57 55499
61 60...

result:

ok n=100000

Test #13:

score: 0
Accepted
time: 163ms
memory: 31988kb

input:

100000
33 43 47 65 67 82 88 95 96 113 130 133 140 232 262 266 282 286 298 299 303 324 326 342 352 354 356 359 362 363 364 369 392 398 408 435 442 454 460 489 508 518 537 556 572 574 580 592 613 616 629 650 652 674 684 718 721 724 732 734 801 809 819 831 845 853 856 878 879 895 897 935 946 956 958 96...

output:

Yes
163594
1 48701
1 64105
1 74288
1 79992
2 40790
2 50812
2 73805
2 96840
3 60650
3 67482
3 75485
4 2
4 47513
4 93660
5 1
5 39347
5 69609
5 82332
5 86250
5 86868
6 60347
6 91245
7 32424
7 44732
7 70174
7 72116
8 63697
9 8
10 70859
10 76048
10 83863
10 89674
11 7029
11 20923
12 14334
13 12
13 75554
...

result:

ok n=100000

Test #14:

score: 0
Accepted
time: 106ms
memory: 31552kb

input:

100000
38535 3433 18670 53850 31420 79252 3155 90709 7043 47690 20905 66663 16655 77812 19606 78158 23549 54025 44700 24119 42542 85555 31117 68856 35627 37419 26767 46031 72252 71511 80835 47732 77030 61434 51792 98165 71334 70644 79996 87007 93335 56112 86306 3040 10776 30683 80961 96794 12323 656...

output:

Yes
99999
1 5106
2 54518
3 6583
4 54710
5 87828
6 49028
7 77493
8 99216
9 56246
10 61460
11 26740
12 98417
13 29209
14 92332
15 77444
16 48567
17 87051
18 94308
19 32613
20 54034
21 96866
22 37347
23 99719
24 19596
25 73244
26 14892
27 16822
28 96633
29 30430
30 71514
31 83771
32 33922
33 97683
34 1...

result:

ok n=100000

Test #15:

score: 0
Accepted
time: 111ms
memory: 30200kb

input:

100000
1 5 7 8 24 29 32 36 39 41 43 44 46 47 52 54 56 58 59 64 68 69 70 73 75 77 79 82 84 86 88 90 92 93 95 98 99 101 102 104 105 108 112 114 115 116 118 123 126 127 128 133 134 139 140 143 145 147 152 153 154 156 160 161 163 165 169 170 176 178 179 180 184 186 187 188 192 193 195 199 200 204 205 20...

output:

No

result:

ok n=100000

Test #16:

score: 0
Accepted
time: 99ms
memory: 30120kb

input:

100000
1 3 4 7 10 11 13 17 18 19 21 22 25 27 28 29 31 35 36 37 38 42 49 50 53 56 57 58 60 62 63 64 68 70 71 79 80 82 83 85 86 87 88 90 93 94 98 103 105 109 110 111 112 116 121 123 127 134 138 139 142 143 148 151 154 156 158 159 160 162 164 166 168 171 172 173 174 175 176 177 180 184 186 187 189 193 ...

output:

No

result:

ok n=100000

Test #17:

score: 0
Accepted
time: 106ms
memory: 29936kb

input:

100000
1 2 8 9 11 14 19 21 22 24 25 28 33 34 35 36 43 49 51 55 57 59 62 64 68 69 70 71 72 75 76 78 79 80 81 82 83 87 88 89 91 92 98 99 105 106 107 111 112 116 118 123 124 125 128 131 133 138 139 141 142 143 146 147 152 154 155 159 161 162 163 164 165 169 172 173 174 175 179 183 184 185 186 187 190 1...

output:

No

result:

ok n=100000

Test #18:

score: 0
Accepted
time: 110ms
memory: 30348kb

input:

100000
60 134 140 182 208 256 291 327 364 395 404 419 439 444 457 469 486 510 527 561 569 595 611 612 645 654 710 778 792 794 810 832 873 890 900 901 911 914 942 946 978 1022 1057 1060 1083 1094 1095 1146 1154 1155 1280 1323 1336 1368 1379 1388 1395 1480 1500 1509 1548 1573 1580 1597 1601 1622 1629 ...

output:

No

result:

ok n=100000

Test #19:

score: 0
Accepted
time: 135ms
memory: 30036kb

input:

100000
52072 2 3 50731 5 75525 49404 8 52753 2744 11 34189 13 48355 15 16 17 50376 86416 20 21 56114 23 20072 25 53838 48273 63338 29 30 60156 6205 8084 34 35 36 48381 71655 72484 63969 88506 59722 27083 5369 44672 86160 39926 48 49 8962 51 47113 53 69142 55 66271 24245 74454 59 72556 61 35930 86895...

output:

No

result:

ok n=100000

Test #20:

score: 0
Accepted
time: 68ms
memory: 27808kb

input:

100000
13821 33496 19412 85158 61916 61576 41795 39637 42402 12256 37931 7198 19499 24983 15918 19942 56948 7239 17886 24328 17628 63213 4681 90112 37749 17984 25778 75577 33274 43479 47779 64385 77793 82833 15116 96895 87829 30340 25506 7179 48585 77809 44101 91839 93597 69594 37840 3271 4541 68178...

output:

No

result:

ok n=100000

Test #21:

score: 0
Accepted
time: 0ms
memory: 3676kb

input:

1
1
1

output:

Yes
0

result:

ok n=1

Extra Test:

score: 0
Extra Test Passed