QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#360020#5154. ETAkevinyang#WA 1ms4652kbC++171.5kb2024-03-21 09:57:372024-03-21 09:57:38

Judging History

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

  • [2024-03-21 09:57:38]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4652kb
  • [2024-03-21 09:57:37]
  • 提交

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,b

	ka = 5c*(kb-1)
	7c = ka-kb+1;


	*/
	vector<int>vals = {5, 14, 19, 41, 46};
	map<int,int>sz;
	sz[5] = 2;
	sz[14] = sz[19] = 3;
	sz[41] = sz[46] = 4;
	map<int,vector<int>>dx;
	dx[5] = {1,0};
	dx[14] = {1,0,-1};
	dx[19] = {1,1,0};
	dx[41] = {1,2,-1,0};
	dx[46] = {1,1,1,0};
	vector<int>dp(200005);
	dp[0] = 1;
	const int mxn = 200005;
	for(int i = 1; i<mxn; i++){
		for(int nxt: vals){
			if(i-nxt>=0 && dp[i-nxt]){
				dp[i] = nxt;
			}
		}
	}
	a*=100; b*=100;
	int dif = a-(b-1);
	vector<int>ans(b+1,b);
	int cur = 1;
	while(dif > 0){
		int v = dp[dif];
		for(int i = 0; i<sz[v]; i++){
			int val = dx[v][i];
			if(val==0)continue;
			ans[cur+i] = cur+i+val;
		}
		dif-=v;
		cur+=sz[dif];
	}
	cout << b << ' ' << b-1 << '\n';
	for(int i = 1; i<b; i++){
		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: 1ms
memory: 3656kb

input:

1/2

output:

2 1
1 2

result:

ok 

Test #2:

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

input:

1/3

output:

impossible

result:

ok 

Test #3:

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

input:

7/4

output:

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

result:

FAIL Wrong average distance, got 405/400, wanted 7/4