QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#563108#4317. 拯救还是毁灭ElegiaAC ✓145ms66840kbC++232.8kb2024-09-14 02:47:112024-09-14 02:47:11

Judging History

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

  • [2024-09-14 02:47:11]
  • 评测
  • 测评结果:AC
  • 用时:145ms
  • 内存:66840kb
  • [2024-09-14 02:47:11]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

using u32 = unsigned;

struct IO_Tp
{
	const static int _I_Buffer_Size = 8 << 20;
	char _I_Buffer[_I_Buffer_Size], *_I_pos = _I_Buffer;
	
	const static int _O_Buffer_Size = 40 << 20;
	char _O_Buffer[_O_Buffer_Size], *_O_pos = _O_Buffer;
	
	u32 m[10000];
	
	IO_Tp()
	{
		constexpr u32 e0 = '\0\0\0\1', e1 = '\0\0\1\0', e2 = '\0\1\0\0', e3 = '\1\0\0\0';
		int x = 0;
		for (u32 i = 0, c0 = '0000'; i != 10; ++i, c0 += e0)
			for (u32 j = 0, c1 = c0; j != 10; ++j, c1 += e1)
				for (u32 k = 0, c2 = c1; k != 10; ++k, c2 += e2)
					for (u32 l = 0, c3 = c2; l != 10; ++l, c3 += e3)
						m[x++] = c3;
		
		fread(_I_Buffer, 1, _I_Buffer_Size, stdin);
	}
	~IO_Tp() { fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout); }
	
	IO_Tp &operator>>(int &res)
	{
		while (!isdigit(*_I_pos))
			++_I_pos;
		res = *_I_pos++ - '0';
		while (isdigit(*_I_pos))
			res = res * 10 + (*_I_pos++ - '0');
		return *this;
	}
	
	IO_Tp &operator>>(u32 &res)
	{
		while (!isdigit(*_I_pos))
			++_I_pos;
		res = *_I_pos++ - '0';
		while (isdigit(*_I_pos))
			res = res * 10 + (*_I_pos++ - '0');
		return *this;
	}
	
	IO_Tp &operator<<(u32 x)
	{
		if (x == 0)
		{
			*_O_pos++ = '0';
			return *this; 
		}
		static char _buf[35];
		char *_pos = _buf + 35;
		while (x >= 10000)
			*--reinterpret_cast<u32 *&>(_pos) = m[x % 10000], x /= 10000;
		*--reinterpret_cast<u32 *&>(_pos) = m[x];
		_pos += (x < 1000) + (x < 100) + (x < 10);
		_O_pos = std::copy(_pos, _buf + 35, _O_pos);
		return *this;
	}
	
	IO_Tp &operator<<(char ch)
	{
		*_O_pos++ = ch;
		return *this;
	}
} IO;

const int _ = 1005;

int a[_ * _], p[_ * _];
bool vis[_ * _];
int cnt[_];

vector<pair<int, int>> vc;

int N;
void apply(int x, int y) {
	if (x == y) return;
	vc.emplace_back(x, y);
	swap(a[x], a[y]);
	swap(p[a[x]], p[a[y]]);
}

int main() {
	IO >> N;
	for (int i = 0; i != N * N; ++i) {
		IO >> a[i]; p[--a[i]] = i;
	}
	queue<int> Q;
	for (int i = N - 1; i >= 0; --i) {
		memset(cnt, 0, sizeof(cnt));
		for (int j = 0; j != N; ++j) {
			++cnt[p[i * N + j] % N];
		}
		for (int j = 0; j != N; ++j) if (!cnt[j]) Q.push(j);
		while (!Q.empty()) {
			int x = Q.front(); Q.pop();
			int px = p[i * N + x] / N, py = p[i * N + x] % N;
			apply(px * N + py, px * N + x);
			apply(px * N + x, i * N + x);
			if (--cnt[py] == 0) Q.push(py);
		}
		for (int j = 0; j != N; ++j) if (cnt[j]) {
			int px = p[i * N + j] / N, py = p[i * N + j] % N;
			apply(px * N + py, i * N + py);
		}
	}
	for (int i = 0; i != N * N; ++i) {
		while (a[i] != i) {
			apply(a[i], i);
		}
	}

	IO << u32(vc.size()) << '\n';
	for (const auto& [x, y] : vc) {
		IO << u32(x / N + 1) << ' ' << u32(x % N + 1) << ' ' << u32(y / N + 1) << ' ' << u32(y % N + 1) << '\n';
	}
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 59ms
memory: 63304kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1998000
401 24 1000 24
434 232 1000 232
69 420 1000 420
450 261 1000 261
473 737 1000 737
238 198 1000 198
702 700 1000 700
660 324 1000 324
927 14 1000 14
353 870 1000 870
850 335 1000 335
247 327 1000 327
118 206 1000 206
893 346 1000 346
16 686 1000 686
39 764 1000 764
951 743 1000 743
813 643 10...

result:

ok Accepted.

Test #2:

score: 0
Accepted
time: 70ms
memory: 65352kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990286
401 24 1000 24
434 232 1000 232
69 420 1000 420
450 261 1000 261
473 737 1000 737
238 198 1000 198
702 700 1000 700
660 324 1000 324
927 14 1000 14
353 870 1000 870
850 335 1000 335
247 327 1000 327
118 206 1000 206
893 346 1000 346
16 686 1000 686
39 764 1000 764
951 743 1000 743
813 643 10...

result:

ok Accepted.

Test #3:

score: 0
Accepted
time: 83ms
memory: 64360kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990126
401 24 1000 24
434 232 1000 232
69 420 1000 420
450 261 1000 261
473 737 1000 737
238 198 1000 198
702 700 1000 700
660 324 1000 324
927 14 1000 14
353 870 1000 870
850 335 1000 335
247 327 1000 327
118 206 1000 206
893 346 1000 346
16 686 1000 686
39 764 1000 764
951 743 1000 743
813 643 10...

result:

ok Accepted.

Test #4:

score: 0
Accepted
time: 79ms
memory: 64664kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990264
401 24 1000 24
434 232 1000 232
69 420 1000 420
450 261 1000 261
473 737 1000 737
238 198 1000 198
702 700 1000 700
660 324 1000 324
927 14 1000 14
353 870 1000 870
850 335 1000 335
247 327 1000 327
118 206 1000 206
893 346 1000 346
16 686 1000 686
39 764 1000 764
951 743 1000 743
813 643 10...

result:

ok Accepted.

Test #5:

score: 0
Accepted
time: 77ms
memory: 64948kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990206
401 24 1000 24
434 232 1000 232
69 420 1000 420
450 261 1000 261
473 737 1000 737
238 198 1000 198
702 700 1000 700
660 324 1000 324
927 14 1000 14
353 870 1000 870
850 335 1000 335
247 327 1000 327
118 206 1000 206
893 346 1000 346
16 686 1000 686
39 764 1000 764
951 743 1000 743
813 643 10...

result:

ok Accepted.

Test #6:

score: 0
Accepted
time: 70ms
memory: 64536kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990192
654 2 654 551
654 551 1000 551
434 232 434 2
434 2 1000 2
677 120 677 232
677 232 1000 232
314 955 314 120
314 120 1000 120
659 557 659 955
659 955 1000 955
241 922 241 557
241 557 1000 557
128 999 128 922
128 922 1000 922
479 16 479 999
479 999 1000 999
39 764 39 16
39 16 1000 16
27 377 27 ...

result:

ok Accepted.

Test #7:

score: 0
Accepted
time: 87ms
memory: 66508kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990120
762 179 762 298
762 298 1000 298
654 2 654 551
654 551 1000 551
264 781 264 179
264 179 1000 179
434 232 434 2
434 2 1000 2
207 192 207 781
207 781 1000 781
677 120 677 232
677 232 1000 232
396 109 396 192
396 192 1000 192
314 955 314 120
314 120 1000 120
899 185 899 109
899 109 1000 109
659...

result:

ok Accepted.

Test #8:

score: 0
Accepted
time: 72ms
memory: 65748kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990116
762 179 762 298
762 298 1000 298
654 2 654 551
654 551 1000 551
264 781 264 179
264 179 1000 179
434 232 434 2
434 2 1000 2
207 192 207 781
207 781 1000 781
677 120 677 232
677 232 1000 232
396 109 396 192
396 192 1000 192
314 955 314 120
314 120 1000 120
899 185 899 109
899 109 1000 109
659...

result:

ok Accepted.

Test #9:

score: 0
Accepted
time: 91ms
memory: 65424kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990082
951 743 951 17
951 17 1000 17
240 75 240 285
240 285 1000 285
762 179 762 298
762 298 1000 298
725 295 725 436
725 436 1000 436
654 2 654 551
654 551 1000 551
791 165 791 700
791 700 1000 700
46 167 46 958
46 958 1000 958
662 751 662 743
662 743 1000 743
264 781 264 179
264 179 1000 179
859 ...

result:

ok Accepted.

Test #10:

score: 0
Accepted
time: 87ms
memory: 65948kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990088
951 743 951 17
951 17 1000 17
350 546 350 67
350 67 1000 67
174 824 174 101
174 101 1000 101
256 835 256 117
256 117 1000 117
545 367 545 149
545 149 1000 149
715 444 715 247
715 247 1000 247
957 463 957 262
957 262 1000 262
240 75 240 285
240 285 1000 285
762 179 762 298
762 298 1000 298
72...

result:

ok Accepted.

Test #11:

score: 0
Accepted
time: 145ms
memory: 65940kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990120
669 629 669 7
669 7 1000 7
951 743 951 17
951 17 1000 17
813 643 813 18
813 18 1000 18
350 546 350 67
350 67 1000 67
174 824 174 101
174 101 1000 101
265 430 265 104
265 104 1000 104
256 835 256 117
256 117 1000 117
429 963 429 144
429 144 1000 144
545 367 545 149
545 149 1000 149
816 883 81...

result:

ok Accepted.

Test #12:

score: 0
Accepted
time: 60ms
memory: 65912kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1998000
401 24 1000 24
434 232 1000 232
69 420 1000 420
450 261 1000 261
473 737 1000 737
238 198 1000 198
702 700 1000 700
660 324 1000 324
927 14 1000 14
353 870 1000 870
850 335 1000 335
247 327 1000 327
118 206 1000 206
893 346 1000 346
16 686 1000 686
39 764 1000 764
951 743 1000 743
813 643 10...

result:

ok Accepted.

Test #13:

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

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 742824 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1989960
473 737 473 5
473 5 1000 5
367 463 367 7
367 7 1000 7
118 206 118 13
118 13 1000 13
951 743 951 17
951 17 1000 17
813 643 813 18
813 18 1000 18
350 546 350 67
350 67 1000 67
498 906 498 82
498 82 1000 82
174 824 174 101
174 101 1000 101
265 430 265 104
265 104 1000 104
493 46 493 113
493 113...

result:

ok Accepted.

Test #14:

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

input:

1
1

output:

0

result:

ok Accepted.

Test #15:

score: 0
Accepted
time: 70ms
memory: 63228kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1998000
401 24 1000 24
434 232 1000 232
69 420 1000 420
450 261 1000 261
473 737 1000 737
238 198 1000 198
702 700 1000 700
660 324 1000 324
927 14 1000 14
353 870 1000 870
850 335 1000 335
247 327 1000 327
118 206 1000 206
893 346 1000 346
16 686 1000 686
39 764 1000 764
951 743 1000 743
813 643 10...

result:

ok Accepted.

Test #16:

score: 0
Accepted
time: 36ms
memory: 64384kb

input:

1000
378384 378846 378682 378036 378770 378725 378196 378111 378658 378211 378017 378043 378227 378651 378186 378791 378110 378138 378837 378271 378323 378843 378059 378762 378664 378389 378509 378691 378051 378238 378099 378118 378596 378364 378915 378862 378453 378342 378431 378003 378284 378849 3...

output:

1998000
854 671 1000 671
854 407 1000 407
854 40 1000 40
854 554 1000 554
854 995 1000 995
854 577 1000 577
854 486 1000 486
854 431 1000 431
854 854 1000 854
854 660 1000 660
854 560 1000 560
854 457 1000 457
854 740 1000 740
854 268 1000 268
854 382 1000 382
854 483 1000 483
854 11 1000 11
854 295...

result:

ok Accepted.

Test #17:

score: 0
Accepted
time: 51ms
memory: 63896kb

input:

1000
383379 383297 383978 383304 383827 383736 383312 383974 383292 383005 383064 383173 383632 383665 383126 383171 383186 383209 383497 383241 383135 383308 383430 383202 383797 383628 383167 383714 383592 383577 383533 383967 383080 383764 383899 383763 383437 383205 383683 383953 383916 383039 3...

output:

1998000
596 232 1000 232
596 654 1000 654
596 607 1000 607
596 299 1000 299
596 10 1000 10
596 653 1000 653
596 344 1000 344
596 830 1000 830
596 347 1000 347
596 702 1000 702
596 125 1000 125
596 216 1000 216
596 190 1000 190
596 780 1000 780
596 339 1000 339
596 501 1000 501
596 362 1000 362
596 6...

result:

ok Accepted.

Test #18:

score: 0
Accepted
time: 31ms
memory: 42016kb

input:

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

output:

999999
999 1000 1000 1000
998 1000 999 1000
997 1000 998 1000
996 1000 997 1000
995 1000 996 1000
994 1000 995 1000
993 1000 994 1000
992 1000 993 1000
991 1000 992 1000
990 1000 991 1000
989 1000 990 1000
988 1000 989 1000
987 1000 988 1000
986 1000 987 1000
985 1000 986 1000
984 1000 985 1000
983 ...

result:

ok Accepted.

Test #19:

score: 0
Accepted
time: 34ms
memory: 40888kb

input:

1000
1000000 1 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...

output:

999999
1 1 1000 1
1 1 999 1
1 1 998 1
1 1 997 1
1 1 996 1
1 1 995 1
1 1 994 1
1 1 993 1
1 1 992 1
1 1 991 1
1 1 990 1
1 1 989 1
1 1 988 1
1 1 987 1
1 1 986 1
1 1 985 1
1 1 984 1
1 1 983 1
1 1 982 1
1 1 981 1
1 1 980 1
1 1 979 1
1 1 978 1
1 1 977 1
1 1 976 1
1 1 975 1
1 1 974 1
1 1 973 1
1 1 972 1
1 ...

result:

ok Accepted.

Test #20:

score: 0
Accepted
time: 75ms
memory: 65400kb

input:

1000
2 1002 2002 3002 4002 5002 6002 7002 8002 9002 10002 11002 12002 13002 14002 15002 16002 17002 18002 19002 20002 21002 22002 23002 24002 25002 26002 27002 28002 29002 30002 31002 32002 33002 34002 35002 36002 37002 38002 39002 40002 41002 42002 43002 44002 45002 46002 47002 48002 49002 50002 51...

output:

1996501
1000 999 1000 1
1 1000 1 2
1 2 1000 2
2 1000 2 3
2 3 1000 3
3 1000 3 4
3 4 1000 4
4 1000 4 5
4 5 1000 5
5 1000 5 6
5 6 1000 6
6 1000 6 7
6 7 1000 7
7 1000 7 8
7 8 1000 8
8 1000 8 9
8 9 1000 9
9 1000 9 10
9 10 1000 10
10 1000 10 11
10 11 1000 11
11 1000 11 12
11 12 1000 12
12 1000 12 13
12 13...

result:

ok Accepted.

Test #21:

score: 0
Accepted
time: 60ms
memory: 64400kb

input:

1000
383379 383297 383978 383304 383827 383736 383312 383974 383292 383005 383064 383173 383632 383665 383126 383171 383186 383209 383497 383241 383135 383308 383430 383202 383797 383628 383167 383714 383592 383577 383533 383967 383080 383764 383899 383763 383437 383205 383683 383953 383916 383039 3...

output:

1997999
596 232 1000 232
596 654 1000 654
596 607 1000 607
596 299 1000 299
596 10 1000 10
596 653 1000 653
596 344 1000 344
596 830 1000 830
596 347 1000 347
596 702 1000 702
596 125 1000 125
596 216 1000 216
596 190 1000 190
596 780 1000 780
596 339 1000 339
596 501 1000 501
596 362 1000 362
596 6...

result:

ok Accepted.

Test #22:

score: 0
Accepted
time: 52ms
memory: 63348kb

input:

1000
383379 383297 383978 383304 383827 383736 383312 383974 383292 383005 383064 383173 383632 383665 383126 383171 383186 383209 383497 383241 383135 383308 383430 383202 383797 383628 383167 383714 383592 383577 383533 383967 383080 383764 383899 383763 383437 383205 383683 383953 383916 383039 3...

output:

1997998
596 232 1000 232
596 654 1000 654
596 607 1000 607
596 299 1000 299
596 10 1000 10
596 653 1000 653
596 344 1000 344
596 830 1000 830
596 347 1000 347
596 702 1000 702
596 125 1000 125
596 216 1000 216
596 190 1000 190
596 780 1000 780
596 339 1000 339
596 501 1000 501
596 362 1000 362
596 6...

result:

ok Accepted.

Test #23:

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

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1998000
401 24 1000 24
434 232 1000 232
69 420 1000 420
450 261 1000 261
473 737 1000 737
238 198 1000 198
702 700 1000 700
660 324 1000 324
927 14 1000 14
353 870 1000 870
850 335 1000 335
247 327 1000 327
118 206 1000 206
893 346 1000 346
16 686 1000 686
39 764 1000 764
951 743 1000 743
813 643 10...

result:

ok Accepted.

Test #24:

score: 0
Accepted
time: 49ms
memory: 64168kb

input:

1000
383379 383297 383978 383304 383827 383736 383312 383974 383292 383005 383064 383173 383632 383665 383126 383171 383186 383209 383497 383241 383135 383308 383430 383202 383797 383628 383167 383714 383592 383577 383533 383967 383080 383764 383899 383763 383437 383205 383683 383953 383916 383039 3...

output:

1997997
596 232 1000 232
596 654 1000 654
596 607 1000 607
596 299 1000 299
596 10 1000 10
596 653 1000 653
596 344 1000 344
596 830 1000 830
596 347 1000 347
596 702 1000 702
596 125 1000 125
596 216 1000 216
596 190 1000 190
596 780 1000 780
596 339 1000 339
596 501 1000 501
596 362 1000 362
596 6...

result:

ok Accepted.

Test #25:

score: 0
Accepted
time: 52ms
memory: 63484kb

input:

1000
765923 765649 765437 765697 765568 765166 765024 765681 765965 765556 765185 765781 765602 765901 765351 765204 765910 765739 765588 765769 765129 765812 765968 765116 765034 765868 765858 765150 765281 765770 765544 765940 765937 765712 765478 765018 765443 765380 765400 765094 765499 765591 7...

output:

1997996
249 105 1000 105
249 607 1000 607
249 273 1000 273
249 679 1000 679
249 476 1000 476
249 623 1000 623
249 420 1000 420
249 187 1000 187
249 326 1000 326
249 695 1000 695
249 449 1000 449
249 359 1000 359
249 485 1000 485
249 763 1000 763
249 953 1000 953
249 466 1000 466
249 961 1000 961
249...

result:

ok Accepted.

Test #26:

score: 0
Accepted
time: 55ms
memory: 63296kb

input:

1000
546593 546244 546560 546842 546335 546503 546719 546740 546296 546648 546372 546145 546975 546991 546749 546261 546863 546655 546224 546054 546895 546155 546989 546986 546102 546059 546004 546040 546408 546083 546748 546384 546206 546405 546908 546565 546431 546822 546783 546641 546418 546915 5...

output:

1997995
437 861 1000 861
437 438 1000 438
437 212 1000 212
437 27 1000 27
437 264 1000 264
437 674 1000 674
437 884 1000 884
437 195 1000 195
437 290 1000 290
437 186 1000 186
437 723 1000 723
437 76 1000 76
437 917 1000 917
437 315 1000 315
437 493 1000 493
437 835 1000 835
437 352 1000 352
437 266...

result:

ok Accepted.

Test #27:

score: 0
Accepted
time: 52ms
memory: 63252kb

input:

1000
245814 245896 245217 245160 245517 245789 245688 245243 245869 245548 245479 245226 245868 245331 245543 245629 245529 245780 245057 245567 245406 245454 245206 245415 245139 245416 245382 245039 245937 245267 245038 245787 245859 245892 245597 245536 245376 245846 245275 245307 245485 245430 2...

output:

1997994
964 297 1000 297
964 591 1000 591
964 971 1000 971
964 841 1000 841
964 148 1000 148
964 860 1000 860
964 94 1000 94
964 835 1000 835
964 834 1000 834
964 365 1000 365
964 604 1000 604
964 323 1000 323
964 339 1000 339
964 413 1000 413
964 458 1000 458
964 907 1000 907
964 246 1000 246
964 3...

result:

ok Accepted.

Test #28:

score: 0
Accepted
time: 51ms
memory: 64016kb

input:

1000
61557 61538 61992 61418 61459 61224 61009 61367 61604 61243 61423 61873 61774 61436 61466 61011 61671 61260 61308 61856 61622 61332 61984 61422 61645 61548 61419 61435 61165 61664 61340 61520 61182 61649 61043 61874 61024 61307 61797 61837 61795 61802 61900 61388 61836 61144 61064 61351 61740 6...

output:

1997993
742 219 1000 219
742 961 1000 961
742 126 1000 126
742 482 1000 482
742 105 1000 105
742 481 1000 481
742 835 1000 835
742 62 1000 62
742 7 1000 7
742 515 1000 515
742 16 1000 16
742 556 1000 556
742 986 1000 986
742 641 1000 641
742 764 1000 764
742 669 1000 669
742 224 1000 224
742 469 100...

result:

ok Accepted.

Test #29:

score: 0
Accepted
time: 57ms
memory: 64280kb

input:

1000
996685 996990 996192 996880 996864 996813 996152 996416 996490 996815 996429 996877 996274 996981 996865 996133 996918 996203 996594 996222 996849 996243 996832 996684 996586 996704 996703 996007 996097 996147 996190 996188 996965 996057 996076 996632 996229 996174 996678 996602 996963 996206 9...

output:

1997992
582 642 1000 642
582 891 1000 891
582 574 1000 574
582 593 1000 593
582 898 1000 898
582 230 1000 230
582 28 1000 28
582 543 1000 543
582 163 1000 163
582 844 1000 844
582 329 1000 329
582 989 1000 989
582 587 1000 587
582 599 1000 599
582 463 1000 463
582 741 1000 741
582 656 1000 656
582 4...

result:

ok Accepted.

Test #30:

score: 0
Accepted
time: 43ms
memory: 63792kb

input:

1000
335743 335130 335163 335806 335670 335141 335943 335395 335599 335515 335230 335687 335598 335233 335243 335478 335454 335447 335795 335610 335790 335298 335480 335392 335965 335237 335193 335913 335889 335097 335414 335323 335458 335049 335682 335178 335361 335117 335509 335405 335155 335643 3...

output:

1997991
864 279 1000 279
864 47 1000 47
864 814 1000 814
864 827 1000 827
864 310 1000 310
864 699 1000 699
864 148 1000 148
864 135 1000 135
864 296 1000 296
864 88 1000 88
864 299 1000 299
864 811 1000 811
864 381 1000 381
864 346 1000 346
864 893 1000 893
864 499 1000 499
864 211 1000 211
864 466...

result:

ok Accepted.

Test #31:

score: 0
Accepted
time: 56ms
memory: 64812kb

input:

1000
572459 572682 572811 572715 572911 572627 572137 572476 572893 572536 572732 572728 572092 572885 572750 572853 572867 572143 572883 572626 572469 572850 572378 572238 572513 572663 572537 572514 572823 572533 572983 572488 572518 572970 572275 572685 572709 572915 572145 572721 572636 572611 5...

output:

1997999
770 763 1000 763
770 769 1000 769
770 626 1000 626
770 568 1000 568
770 512 1000 512
770 818 1000 818
770 186 1000 186
770 86 1000 86
770 955 1000 955
770 60 1000 60
770 377 1000 377
770 339 1000 339
770 960 1000 960
770 945 1000 945
770 431 1000 431
770 381 1000 381
770 897 1000 897
770 663...

result:

ok Accepted.

Test #32:

score: 0
Accepted
time: 48ms
memory: 66060kb

input:

1000
560571 560121 560859 560154 560235 560862 560729 560218 560048 560834 560772 560351 560458 560413 560960 560089 560411 560068 560593 560671 560150 560369 560826 560330 560064 560013 560594 560409 560775 560077 560617 560237 560763 560554 560848 560869 560138 560454 560249 560083 560661 560450 5...

output:

1997998
453 473 1000 473
453 854 1000 854
453 901 1000 901
453 970 1000 970
453 692 1000 692
453 320 1000 320
453 924 1000 924
453 414 1000 414
453 509 1000 509
453 49 1000 49
453 353 1000 353
453 305 1000 305
453 26 1000 26
453 839 1000 839
453 571 1000 571
453 634 1000 634
453 72 1000 72
453 281 1...

result:

ok Accepted.

Test #33:

score: 0
Accepted
time: 59ms
memory: 66752kb

input:

1000
598160 598843 598010 598357 598885 598475 598861 598480 598441 598457 598228 598823 598020 598523 598864 598088 598474 598544 598151 598873 598535 598409 598538 598665 598103 598101 598403 598871 598892 598851 598816 598219 598597 598989 598844 598614 598098 598332 598852 598251 598909 598473 5...

output:

1997997
252 694 1000 694
252 865 1000 865
252 927 1000 927
252 917 1000 917
252 403 1000 403
252 809 1000 809
252 179 1000 179
252 951 1000 951
252 611 1000 611
252 3 1000 3
252 713 1000 713
252 575 1000 575
252 153 1000 153
252 826 1000 826
252 238 1000 238
252 964 1000 964
252 697 1000 697
252 87 ...

result:

ok Accepted.

Test #34:

score: 0
Accepted
time: 72ms
memory: 64148kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1998000
401 24 1000 24
434 232 1000 232
69 420 1000 420
450 261 1000 261
473 737 1000 737
238 198 1000 198
702 700 1000 700
660 324 1000 324
927 14 1000 14
353 870 1000 870
850 335 1000 335
247 327 1000 327
118 206 1000 206
893 346 1000 346
16 686 1000 686
39 764 1000 764
951 743 1000 743
813 643 10...

result:

ok Accepted.

Test #35:

score: 0
Accepted
time: 53ms
memory: 64508kb

input:

1000
556261 556653 556726 556247 556206 556107 556120 556211 556540 556334 556145 556239 556097 556734 556476 556244 556401 556470 556005 556884 556699 556936 556696 556587 556602 556264 556919 556458 556555 556159 556003 556778 556209 556631 556009 556558 556478 556396 556771 556550 556348 556687 5...

output:

1997996
474 407 1000 407
474 594 1000 594
474 31 1000 31
474 462 1000 462
474 19 1000 19
474 982 1000 982
474 443 1000 443
474 68 1000 68
474 35 1000 35
474 182 1000 182
474 415 1000 415
474 834 1000 834
474 81 1000 81
474 927 1000 927
474 481 1000 481
474 395 1000 395
474 729 1000 729
474 917 1000 ...

result:

ok Accepted.

Test #36:

score: 0
Accepted
time: 54ms
memory: 64056kb

input:

1000
95449 95943 95602 95263 95644 95061 95279 95813 95740 95242 95951 95803 95352 95696 95234 95841 95645 95953 95156 95923 95509 95368 95764 95533 95364 95265 95689 95850 95430 95978 95746 95556 95679 95587 95250 95799 95520 95779 95539 95333 95722 95889 95989 95670 95899 95654 95003 95920 95150 9...

output:

1997902
152 280 152 225
152 225 1000 225
152 431 152 280
152 280 1000 280
152 806 152 431
152 431 1000 431
152 528 152 806
152 806 1000 806
152 805 152 528
152 528 1000 528
152 363 152 805
152 805 1000 805
152 513 152 363
152 363 1000 363
152 991 152 513
152 513 1000 513
152 351 152 991
152 991 1000...

result:

ok Accepted.

Test #37:

score: 0
Accepted
time: 65ms
memory: 65984kb

input:

1000
957448 957161 957642 957882 957356 957099 957743 957390 957589 957676 957377 957868 957239 957063 957961 957996 957341 957324 957673 957716 957912 957824 957633 957343 957611 957656 957627 957342 957022 957152 957068 957859 957411 957388 957646 957809 957540 957067 957208 957112 957751 957015 9...

output:

1997782
736 234 1000 234
736 608 1000 608
736 114 1000 114
736 914 1000 914
736 891 1000 891
736 320 1000 320
736 317 1000 317
736 97 1000 97
736 566 1000 566
736 609 1000 609
736 280 1000 280
736 351 1000 351
736 197 1000 197
736 758 1000 758
736 42 1000 42
736 638 1000 638
736 652 1000 652
736 404...

result:

ok Accepted.

Test #38:

score: 0
Accepted
time: 61ms
memory: 64228kb

input:

1000
60816 60166 60381 60643 60789 60512 60070 60017 60202 60063 60104 60853 60368 60399 60504 60254 60373 60980 60116 60003 60493 60222 60187 60676 60314 60798 60554 60653 60207 60278 60217 60501 60507 60074 60110 60686 60487 60647 60065 60426 60893 60161 60047 60359 60878 60821 60127 60077 60423 6...

output:

1997590
173 112 173 137
173 137 1000 137
173 288 173 112
173 112 1000 112
173 348 173 288
173 288 1000 288
173 81 173 348
173 348 1000 348
173 661 173 81
173 81 1000 81
173 91 173 661
173 661 1000 661
173 626 173 91
173 91 1000 91
173 479 173 626
173 626 1000 626
173 690 173 479
173 479 1000 479
173...

result:

ok Accepted.

Test #39:

score: 0
Accepted
time: 59ms
memory: 64524kb

input:

1000
24647 24015 24359 24034 24755 24059 24886 24037 24547 24668 24108 24396 24575 24065 24243 24267 24289 24914 24299 24479 25000 24348 24020 24984 24472 24176 24062 24453 24915 24561 24229 24136 24463 24943 24551 24741 24569 24959 24500 24505 24281 24493 24251 24358 24385 24439 24067 24095 24345 2...

output:

1997176
79 203 79 351
79 351 1000 351
79 257 79 603
79 603 1000 603
79 193 79 203
79 203 1000 203
79 780 79 257
79 257 1000 257
79 374 79 193
79 193 1000 193
79 476 79 780
79 780 1000 780
79 658 79 374
79 374 1000 374
79 769 79 476
79 476 1000 476
79 358 79 658
79 658 1000 658
79 789 79 769
79 769 1...

result:

ok Accepted.

Test #40:

score: 0
Accepted
time: 69ms
memory: 64384kb

input:

1000
331539 331151 331975 331601 331812 331879 331223 331408 331843 331333 331996 331947 331912 331815 331770 331659 331282 331390 331549 331329 331262 331138 331003 331714 331529 331146 331167 331790 331598 331981 331787 331425 331637 331654 331431 331968 331621 331074 331448 331391 331832 331645 3...

output:

1996502
781 296 781 14
781 14 1000 14
781 689 781 230
781 230 1000 230
781 524 781 501
781 501 1000 501
781 947 781 296
781 296 1000 296
781 637 781 689
781 689 1000 689
781 362 781 524
781 524 1000 524
781 12 781 947
781 947 1000 947
781 33 781 637
781 637 1000 637
781 897 781 362
781 362 1000 362
...

result:

ok Accepted.

Test #41:

score: 0
Accepted
time: 65ms
memory: 65096kb

input:

1000
545268 545435 545452 545916 545410 545648 545938 545405 545776 545017 545588 545887 545053 545614 545579 545130 545502 545057 545581 545421 545088 545815 545276 545688 545429 545947 545690 545522 545496 545723 724634 545868 545575 545876 545303 545367 545180 545464 545501 545274 545059 545081 5...

output:

1995686
538 365 538 259
538 259 1000 259
538 920 538 307
538 307 1000 307
538 6 538 648
538 648 1000 648
538 938 538 667
538 667 1000 667
538 574 538 875
538 875 1000 875
538 580 538 365
538 365 1000 365
538 739 538 920
538 920 1000 920
538 755 538 6
538 6 1000 6
538 7 538 938
538 938 1000 938
538 2...

result:

ok Accepted.

Test #42:

score: 0
Accepted
time: 75ms
memory: 66160kb

input:

1000
854919 854197 854949 854159 854732 854190 854561 854846 854266 854264 854736 854984 854714 854367 854665 854105 854717 854883 854698 854037 854543 854139 854413 854472 854876 854279 854570 854483 854990 854492 854576 854648 854049 854811 854660 854605 854184 854112 854553 854093 854103 854563 8...

output:

1994700
587 485 587 133
587 133 1000 133
587 508 587 142
587 142 1000 142
587 84 587 218
587 218 1000 218
587 54 587 403
587 403 1000 403
587 865 587 449
587 449 1000 449
587 201 587 455
587 455 1000 455
587 249 587 463
587 463 1000 463
587 246 587 533
587 533 1000 533
587 1000 587 703
587 703 1000 ...

result:

ok Accepted.

Test #43:

score: 0
Accepted
time: 73ms
memory: 64592kb

input:

1000
591079 591433 591985 591891 591534 591576 591774 591351 591039 591650 591852 591741 591792 591260 591776 591878 595243 591947 591975 591071 591643 591110 591680 591601 591310 591956 591610 591525 591256 591457 591778 591400 591319 591584 591882 591365 591143 591825 591660 677358 591608 591511 5...

output:

1993850
862 263 862 10
862 10 1000 10
862 482 862 38
862 38 1000 38
862 682 862 53
862 53 1000 53
862 377 862 76
862 76 1000 76
862 379 862 95
862 95 1000 95
862 83 862 129
862 129 1000 129
862 895 862 164
862 164 1000 164
862 535 862 174
862 174 1000 174
862 178 862 374
862 374 1000 374
862 559 862...

result:

ok Accepted.

Test #44:

score: 0
Accepted
time: 71ms
memory: 66248kb

input:

1000
178582 178716 115203 178547 178946 178469 178602 178019 178344 921655 178082 178169 178504 178893 178027 178441 433666 178446 341788 178095 178520 178963 178952 178707 178696 178680 178722 178163 178231 178065 178635 178869 178703 178492 178149 178207 178221 178724 178498 178821 178763 178455 1...

output:

1992922
416 169 416 2
416 2 1000 2
416 19 416 7
416 7 1000 7
416 760 416 32
416 32 1000 32
416 647 416 55
416 55 1000 55
416 17 416 80
416 80 1000 80
416 20 416 95
416 95 1000 95
416 883 416 112
416 112 1000 112
416 433 416 119
416 119 1000 119
416 252 416 122
416 122 1000 122
117 859 117 124
117 12...

result:

ok Accepted.

Test #45:

score: 0
Accepted
time: 79ms
memory: 66840kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990867
401 24 1000 24
434 232 1000 232
69 420 1000 420
450 261 1000 261
473 737 1000 737
238 198 1000 198
702 700 1000 700
660 324 1000 324
927 14 1000 14
353 870 1000 870
850 335 1000 335
247 327 1000 327
118 206 1000 206
893 346 1000 346
16 686 1000 686
39 764 1000 764
951 743 1000 743
813 643 10...

result:

ok Accepted.

Test #46:

score: 0
Accepted
time: 62ms
memory: 66512kb

input:

1000
471689 471319 471406 471740 471640 471038 471566 471232 471127 471889 471205 471125 471429 471645 471835 471247 471929 471750 471151 471197 471897 471767 471891 471785 471552 471718 471628 471202 471399 471943 471727 2874 471236 471560 471241 471224 471915 471323 471636 471624 19811 471649 4715...

output:

1992054
821 815 821 12
821 12 1000 12
821 707 821 16
821 16 1000 16
214 903 214 21
214 21 1000 21
821 572 821 47
821 47 1000 47
821 574 821 65
821 65 1000 65
821 329 821 72
821 72 1000 72
821 819 821 82
821 82 1000 82
821 83 821 90
821 90 1000 90
821 690 821 96
821 96 1000 96
821 496 821 110
821 110...

result:

ok Accepted.

Test #47:

score: 0
Accepted
time: 76ms
memory: 65984kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1991000
401 24 1000 24
434 232 1000 232
69 420 1000 420
450 261 1000 261
473 737 1000 737
238 198 1000 198
702 700 1000 700
660 324 1000 324
927 14 1000 14
353 870 1000 870
850 335 1000 335
247 327 1000 327
118 206 1000 206
893 346 1000 346
16 686 1000 686
39 764 1000 764
951 743 1000 743
813 643 10...

result:

ok Accepted.

Test #48:

score: 0
Accepted
time: 85ms
memory: 64812kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990552
401 24 1000 24
434 232 1000 232
69 420 1000 420
450 261 1000 261
473 737 1000 737
238 198 1000 198
702 700 1000 700
660 324 1000 324
927 14 1000 14
353 870 1000 870
850 335 1000 335
247 327 1000 327
118 206 1000 206
893 346 1000 346
16 686 1000 686
39 764 1000 764
951 743 1000 743
813 643 10...

result:

ok Accepted.

Test #49:

score: 0
Accepted
time: 80ms
memory: 65028kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990548
401 24 1000 24
434 232 1000 232
69 420 1000 420
450 261 1000 261
473 737 1000 737
238 198 1000 198
702 700 1000 700
660 324 1000 324
927 14 1000 14
353 870 1000 870
850 335 1000 335
247 327 1000 327
118 206 1000 206
893 346 1000 346
16 686 1000 686
39 764 1000 764
951 743 1000 743
813 643 10...

result:

ok Accepted.

Test #50:

score: 0
Accepted
time: 79ms
memory: 64920kb

input:

1000
921156 164917 876716 346601 859849 128010 597453 517820 153764 816228 42630 968115 720674 725887 873481 472730 923921 922689 526667 758819 770342 216266 971717 759305 966908 301482 74863 561426 880217 783710 560336 923860 491882 553154 530791 476240 818078 877946 148671 206130 898917 24153 5407...

output:

1990202
401 24 1000 24
434 232 1000 232
69 420 1000 420
450 261 1000 261
473 737 1000 737
238 198 1000 198
702 700 1000 700
660 324 1000 324
927 14 1000 14
353 870 1000 870
850 335 1000 335
247 327 1000 327
118 206 1000 206
893 346 1000 346
16 686 1000 686
39 764 1000 764
951 743 1000 743
813 643 10...

result:

ok Accepted.