QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#360037#5154. ETAkevinyang#WA 7ms10496kbC++171.3kb2024-03-21 10:27:232024-03-21 10:27:23

Judging History

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

  • [2024-03-21 10:27:23]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:10496kb
  • [2024-03-21 10:27:23]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
pair<int,int> parse(string s){
	for(int i = 0; i<s.size(); i++){
		if(s[i]=='/'){
			int a = stoll(s.substr(0,i));
			int b = stoll(s.substr(i+1));
			return make_pair(a,b);
		}
	}
	return {0,0};
}
signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	/*
	anything < 1 that's not n-1/n is not possible
	n-1/n is possible
	1/1 is possible

	
	*/
	string s;
	cin >> s;
	auto [a,b] = parse(s);
	if(a<b-1){
		cout << "impossible\n";
		return 0;
	}
	if(a<b){
		cout << b << ' ' << b-1 << '\n';
		for(int i = 1; i<b; i++){
			cout << i << ' ' << b << '\n';
		}
		return 0;
	}
	a*=100000/b; b*=100000/b;
	vector<int>ans(b+1,b);
	int dif = a-(b-1);
	int cur = 1;
	int r = b-1;
	while(dif>0){
		int v = 1;
		for(int i = 1; i<=100000; i++){
			if(i*(i+1)/2<=dif){
				v = i;
			}
			else{
				break;
			}
		}
		dif-=v*(v+1)/2;
		ans[cur] = r;
		for(int i = 1; i<v; i++){
			ans[cur+i] = cur+i-1;
		}
		r--;
		cur+=v;
		//cout << v << '\n';
	}
	vector<vector<int>>adj(b+1);
	cout << b << ' ' << b-1 << '\n';
	for(int i = 1; i<b; i++){
		int x = i+1;
		int y = ans[i]%b+1;
		adj[x].push_back(y);
		adj[y].push_back(x);
		cout << i+1 << ' ' << ans[i]%b+1 << '\n';
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1/2

output:

2 1
1 2

result:

ok 

Test #2:

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

input:

1/3

output:

impossible

result:

ok 

Test #3:

score: 0
Accepted
time: 7ms
memory: 10496kb

input:

7/4

output:

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

result:

ok 

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3656kb

input:

974/975

output:

975 974
1 975
2 975
3 975
4 975
5 975
6 975
7 975
8 975
9 975
10 975
11 975
12 975
13 975
14 975
15 975
16 975
17 975
18 975
19 975
20 975
21 975
22 975
23 975
24 975
25 975
26 975
27 975
28 975
29 975
30 975
31 975
32 975
33 975
34 975
35 975
36 975
37 975
38 975
39 975
40 975
41 975
42 975
43 975
...

result:

FAIL Wrong average distance, got 1947/975, wanted 974/975