QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#320505#8215. Isomorphic Delightucup-team266#AC ✓535ms41980kbC++144.4kb2024-02-03 17:26:122024-02-03 17:26:12

Judging History

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

  • [2024-02-03 17:26:12]
  • 评测
  • 测评结果:AC
  • 用时:535ms
  • 内存:41980kb
  • [2024-02-03 17:26:12]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef array<int, 3> ai3;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int Mod = 1e9 + 7;
inline int sign(int a){ return (a&1) ? (Mod-1) : 1; }
inline void uadd(int &a, int b){ a += b-Mod; a += (a>>31) & Mod; }
inline void usub(int &a, int b){ a -= b, a += (a>>31) & Mod; }
inline void umul(int &a, int b){ a = (int)(1ll * a * b % Mod); }
inline int add(int a, int b){ a += b-Mod; a += (a>>31) & Mod; return a; }
inline int sub(int a, int b){ a -= b, a += (a>>31) & Mod; return a; }
inline int mul(int a, int b){ a = (int)(1ll * a * b % Mod); return a; }
int qpow(int b, ll p){ int ret = 1; while(p){ if(p&1) umul(ret, b); umul(b, b), p >>= 1; } return ret; }
const int fN = 4040;
int fact[fN], invfact[fN], pw2[fN], invpw2[fN], inv[fN];
void initfact(int n){
	pw2[0] = 1; for(int i = 1; i <= n; ++i) pw2[i] = mul(pw2[i-1], 2);
	invpw2[0] = 1; for(int i = 1; i <= n; ++i) invpw2[i] = mul(invpw2[i-1], (Mod+1) / 2);
	fact[0] = 1; for(int i = 1; i <= n; ++i) fact[i] = mul(fact[i-1], i);
	invfact[n] = qpow(fact[n], Mod-2); for(int i = n; i > 0; --i) invfact[i-1] = mul(invfact[i], i);
	for(int i = 1; i <= n; ++i) inv[i] = mul(invfact[i], fact[i-1]);
}
int binom(int n, int m){ return (m < 0 || m > n) ? 0 : mul(fact[n], mul(invfact[m], invfact[n-m])); }
const double pi = acos(-1);
inline void chmax(int &a, int b){ (b>a) ? (a=b) : 0; }
inline void chmin(int &a, int b){ (b<a) ? (a=b) : 0; }

vector<vi> f[30], g[30], tmp[33], v[33];
void solve(){
	f[1].push_back((vi){});
	for(int m = 1; m <= 11; ++m){
		//cout << m << endl;
		//rep(i, 21) cout << (int)f[i].size() << " ";
		//cout << "\n";
		rep(i, 21) g[i].clear();
		function<void(vi, int)> dfs = [&](vi cur, int id){
			int len = (int)cur.size();
			if(len + m > 11 || id >= (int)f[m].size())
				return g[len + 1].push_back(cur), void();
			dfs(cur, id + 1);
			if(len + m <= 11){
				cur.push_back(0);
				for(auto x : f[m][id])
					cur.push_back(len + 1 + x);
				dfs(cur, id + 1);
			}
		};
		for(int i = 11; i >= 0; --i){
			for(auto x : f[i])
				dfs(x, 0);
		}
		rep(i, 21) g[i].swap(f[i]);
	}
	
	//cerr << 1. * clock() / CLOCKS_PER_SEC << "\n";

	v[1].push_back((vi){});
	for(int n = 2; n <= 21; ++n){
		rep(i, n+1) tmp[i].clear();
		tmp[1].push_back((vi){});
		for(int m = 1; m < (n+1) / 2; ++m){
			function<void(vi, int)> dfs = [&](vi cur, int id){
				int len = (int)cur.size();
				if(id >= (int)f[m].size())
					return g[len + 1].push_back(cur), void();
				dfs(cur, id + 1);
				if(len + m <= n){
					cur.push_back(0);
					for(auto x : f[m][id])
						cur.push_back(len + 1 + x);
					dfs(cur, id + 1);
				}
			};
			rep(i, n+1) g[i].clear();
			for(int i = n; i >= 0; --i){
				for(auto x : tmp[i])
					dfs(x, 0);
			}
			rep(i, n+1) g[i].swap(tmp[i]);
		}
		v[n] = tmp[n];
		if(n % 2 == 0){
			rep(i, (int)f[n/2].size()) rep(j, i){
				vi y = f[n/2][i], &x = f[n/2][j];
				y.push_back(0);
				rep(k, (int)x.size())
					y.push_back(x[k] + n/2);
				v[n].push_back(y);
			}
		}
		//cout << n << ": " << (int)v[n].size() << endl;
		//if(n <= 10){
		//	for(auto x : v[n]){
		//		rep(i, n-1)
		//			cout << x[i] << " ";
		//		cout << "\n";
		//	}
		//}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	solve();

	//cerr << 1. * clock() / CLOCKS_PER_SEC << "\n";

	int n;
	cin >> n;

	if(n == 1){
		cout << "YES\n0\n";
	} else if(n <= 5){
		cout << "NO\n";
	} else if(n <= 6){
		cout << "YES\n6\n1 2\n2 3\n1 3\n3 4\n2 5\n5 6\n";
	} else {
		vector<pii> ans;
		int np = 0, lst = 0;
		for(int i = 1; i <= 21; ++i){
			for(auto x : v[i]){
				if(np + i > n){
					rep(j, lst - 1) ans.pop_back();
					np -= lst;
					ans.emplace_back(np, np+1);
					ans.emplace_back(np+1, np+2);
					ans.emplace_back(np+1, np+3);
					ans.emplace_back(np+3, np+4);
					ans.emplace_back(np, np+5);
					for(int i = np+5; i+1 < n; ++i)
						ans.emplace_back(i, i+1);
					np = n;
					break;
				}
				rep(j, (int)x.size())
					ans.emplace_back(np + x[j], np + j + 1);
				np += i, lst = i;
			}
			if(np >= n) break;
		}
		cout << "YES\n" << (int)ans.size() << "\n";
		for(auto x : ans)
			cout << x.first+1 << " " << x.second+1 << "\n";
	}

	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 452ms
memory: 31296kb

input:

1

output:

YES
0

result:

ok Everything ok

Test #2:

score: 0
Accepted
time: 457ms
memory: 31312kb

input:

6

output:

YES
6
1 2
2 3
1 3
3 4
2 5
5 6

result:

ok Everything ok

Test #3:

score: 0
Accepted
time: 468ms
memory: 31316kb

input:

4

output:

NO

result:

ok Everything ok

Test #4:

score: 0
Accepted
time: 458ms
memory: 31296kb

input:

2

output:

NO

result:

ok Everything ok

Test #5:

score: 0
Accepted
time: 460ms
memory: 31592kb

input:

3

output:

NO

result:

ok Everything ok

Test #6:

score: 0
Accepted
time: 457ms
memory: 31388kb

input:

5

output:

NO

result:

ok Everything ok

Test #7:

score: 0
Accepted
time: 450ms
memory: 31424kb

input:

7

output:

YES
6
1 2
2 3
2 4
4 5
1 6
6 7

result:

ok Everything ok

Test #8:

score: 0
Accepted
time: 453ms
memory: 31768kb

input:

8

output:

YES
6
2 3
2 4
4 5
2 6
6 7
7 8

result:

ok Everything ok

Test #9:

score: 0
Accepted
time: 452ms
memory: 31756kb

input:

9

output:

YES
7
2 3
3 4
3 5
5 6
2 7
7 8
8 9

result:

ok Everything ok

Test #10:

score: 0
Accepted
time: 459ms
memory: 31340kb

input:

10

output:

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

result:

ok Everything ok

Test #11:

score: 0
Accepted
time: 455ms
memory: 31428kb

input:

11

output:

YES
9
2 3
3 4
3 5
5 6
2 7
7 8
8 9
9 10
10 11

result:

ok Everything ok

Test #12:

score: 0
Accepted
time: 463ms
memory: 31576kb

input:

12

output:

YES
10
2 3
3 4
3 5
5 6
2 7
7 8
8 9
9 10
10 11
11 12

result:

ok Everything ok

Test #13:

score: 0
Accepted
time: 457ms
memory: 31608kb

input:

13

output:

YES
11
2 3
3 4
3 5
5 6
2 7
7 8
8 9
9 10
10 11
11 12
12 13

result:

ok Everything ok

Test #14:

score: 0
Accepted
time: 461ms
memory: 31768kb

input:

14

output:

YES
12
2 3
3 4
3 5
5 6
2 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14

result:

ok Everything ok

Test #15:

score: 0
Accepted
time: 451ms
memory: 31388kb

input:

15

output:

YES
13
2 3
3 4
3 5
5 6
2 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15

result:

ok Everything ok

Test #16:

score: 0
Accepted
time: 464ms
memory: 31424kb

input:

16

output:

YES
13
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
11 12
9 13
13 14
13 15
15 16

result:

ok Everything ok

Test #17:

score: 0
Accepted
time: 459ms
memory: 31388kb

input:

17

output:

YES
14
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
10 12
12 13
9 14
14 15
15 16
16 17

result:

ok Everything ok

Test #18:

score: 0
Accepted
time: 448ms
memory: 31344kb

input:

18

output:

YES
15
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
10 12
12 13
9 14
14 15
15 16
16 17
17 18

result:

ok Everything ok

Test #19:

score: 0
Accepted
time: 455ms
memory: 31756kb

input:

19

output:

YES
16
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
10 12
12 13
9 14
14 15
15 16
16 17
17 18
18 19

result:

ok Everything ok

Test #20:

score: 0
Accepted
time: 457ms
memory: 31532kb

input:

598

output:

YES
544
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
11 12
9 13
13 14
13 15
15 16
17 18
17 19
19 20
20 21
17 22
22 23
23 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
31 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
51 52
52 53
54 55
55 56
54 57
57 58
58 59
...

result:

ok Everything ok

Test #21:

score: 0
Accepted
time: 464ms
memory: 31460kb

input:

245

output:

YES
221
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
11 12
9 13
13 14
13 15
15 16
17 18
17 19
19 20
20 21
17 22
22 23
23 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
31 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
51 52
52 53
54 55
55 56
54 57
57 58
58 59
...

result:

ok Everything ok

Test #22:

score: 0
Accepted
time: 454ms
memory: 31576kb

input:

793

output:

YES
724
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
11 12
9 13
13 14
13 15
15 16
17 18
17 19
19 20
20 21
17 22
22 23
23 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
31 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
51 52
52 53
54 55
55 56
54 57
57 58
58 59
...

result:

ok Everything ok

Test #23:

score: 0
Accepted
time: 455ms
memory: 31548kb

input:

133

output:

YES
119
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
11 12
9 13
13 14
13 15
15 16
17 18
17 19
19 20
20 21
17 22
22 23
23 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
31 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
51 52
52 53
54 55
55 56
54 57
57 58
58 59
...

result:

ok Everything ok

Test #24:

score: 0
Accepted
time: 454ms
memory: 31692kb

input:

681

output:

YES
620
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
11 12
9 13
13 14
13 15
15 16
17 18
17 19
19 20
20 21
17 22
22 23
23 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
31 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
51 52
52 53
54 55
55 56
54 57
57 58
58 59
...

result:

ok Everything ok

Test #25:

score: 0
Accepted
time: 459ms
memory: 31712kb

input:

922

output:

YES
843
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
11 12
9 13
13 14
13 15
15 16
17 18
17 19
19 20
20 21
17 22
22 23
23 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
31 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
51 52
52 53
54 55
55 56
54 57
57 58
58 59
...

result:

ok Everything ok

Test #26:

score: 0
Accepted
time: 457ms
memory: 31704kb

input:

876

output:

YES
800
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
11 12
9 13
13 14
13 15
15 16
17 18
17 19
19 20
20 21
17 22
22 23
23 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
31 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
51 52
52 53
54 55
55 56
54 57
57 58
58 59
...

result:

ok Everything ok

Test #27:

score: 0
Accepted
time: 448ms
memory: 31624kb

input:

7740

output:

YES
7191
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
11 12
9 13
13 14
13 15
15 16
17 18
17 19
19 20
20 21
17 22
22 23
23 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
31 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
51 52
52 53
54 55
55 56
54 57
57 58
58 59...

result:

ok Everything ok

Test #28:

score: 0
Accepted
time: 464ms
memory: 31528kb

input:

2460

output:

YES
2268
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
11 12
9 13
13 14
13 15
15 16
17 18
17 19
19 20
20 21
17 22
22 23
23 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
31 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
51 52
52 53
54 55
55 56
54 57
57 58
58 59...

result:

ok Everything ok

Test #29:

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

input:

7533

output:

YES
6998
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
11 12
9 13
13 14
13 15
15 16
17 18
17 19
19 20
20 21
17 22
22 23
23 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
31 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
51 52
52 53
54 55
55 56
54 57
57 58
58 59...

result:

ok Everything ok

Test #30:

score: 0
Accepted
time: 458ms
memory: 31536kb

input:

5957

output:

YES
5527
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
11 12
9 13
13 14
13 15
15 16
17 18
17 19
19 20
20 21
17 22
22 23
23 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
31 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
51 52
52 53
54 55
55 56
54 57
57 58
58 59...

result:

ok Everything ok

Test #31:

score: 0
Accepted
time: 470ms
memory: 33220kb

input:

92651

output:

YES
87225
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
11 12
9 13
13 14
13 15
15 16
17 18
17 19
19 20
20 21
17 22
22 23
23 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
31 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
51 52
52 53
54 55
55 56
54 57
57 58
58 5...

result:

ok Everything ok

Test #32:

score: 0
Accepted
time: 464ms
memory: 32484kb

input:

58779

output:

YES
55235
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
11 12
9 13
13 14
13 15
15 16
17 18
17 19
19 20
20 21
17 22
22 23
23 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
31 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
51 52
52 53
54 55
55 56
54 57
57 58
58 5...

result:

ok Everything ok

Test #33:

score: 0
Accepted
time: 452ms
memory: 31580kb

input:

12203

output:

YES
11374
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
11 12
9 13
13 14
13 15
15 16
17 18
17 19
19 20
20 21
17 22
22 23
23 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
31 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
51 52
52 53
54 55
55 56
54 57
57 58
58 5...

result:

ok Everything ok

Test #34:

score: 0
Accepted
time: 463ms
memory: 32288kb

input:

55627

output:

YES
52258
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
11 12
9 13
13 14
13 15
15 16
17 18
17 19
19 20
20 21
17 22
22 23
23 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
31 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
51 52
52 53
54 55
55 56
54 57
57 58
58 5...

result:

ok Everything ok

Test #35:

score: 0
Accepted
time: 467ms
memory: 33216kb

input:

99051

output:

YES
93269
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
11 12
9 13
13 14
13 15
15 16
17 18
17 19
19 20
20 21
17 22
22 23
23 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
31 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
51 52
52 53
54 55
55 56
54 57
57 58
58 5...

result:

ok Everything ok

Test #36:

score: 0
Accepted
time: 527ms
memory: 41844kb

input:

811713

output:

YES
770513
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
11 12
9 13
13 14
13 15
15 16
17 18
17 19
19 20
20 21
17 22
22 23
23 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
31 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
51 52
52 53
54 55
55 56
54 57
57 58
58 ...

result:

ok Everything ok

Test #37:

score: 0
Accepted
time: 485ms
memory: 37744kb

input:

544133

output:

YES
515717
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
11 12
9 13
13 14
13 15
15 16
17 18
17 19
19 20
20 21
17 22
22 23
23 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
31 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
51 52
52 53
54 55
55 56
54 57
57 58
58 ...

result:

ok Everything ok

Test #38:

score: 0
Accepted
time: 476ms
memory: 34544kb

input:

276553

output:

YES
261516
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
11 12
9 13
13 14
13 15
15 16
17 18
17 19
19 20
20 21
17 22
22 23
23 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
31 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
51 52
52 53
54 55
55 56
54 57
57 58
58 ...

result:

ok Everything ok

Test #39:

score: 0
Accepted
time: 530ms
memory: 41980kb

input:

736904

output:

YES
699266
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
11 12
9 13
13 14
13 15
15 16
17 18
17 19
19 20
20 21
17 22
22 23
23 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
31 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
51 52
52 53
54 55
55 56
54 57
57 58
58 ...

result:

ok Everything ok

Test #40:

score: 0
Accepted
time: 535ms
memory: 40768kb

input:

1000000

output:

YES
949834
2 3
2 4
4 5
2 6
6 7
7 8
9 10
10 11
11 12
9 13
13 14
13 15
15 16
17 18
17 19
19 20
20 21
17 22
22 23
23 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
31 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
51 52
52 53
54 55
55 56
54 57
57 58
58 ...

result:

ok Everything ok

Extra Test:

score: 0
Extra Test Passed