QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#360021#5154. ETAkevinyang#WA 2ms4872kbC++171.5kb2024-03-21 10:00:162024-03-21 10:00:16

Judging History

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

  • [2024-03-21 10:00:16]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4872kb
  • [2024-03-21 10:00:16]
  • 提交

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;
		}
		cur+=sz[v];
		dif-=v;
		//cout << dif << '\n';
	}
	cout << b << ' ' << b-1 << '\n';
	for(int i = 1; i<b; i++){
		cout << i+1 << " " << ans[i]%b+1 << '\n';
	}
	return 0;
}

詳細信息

Test #1:

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

input:

1/2

output:

2 1
1 2

result:

ok 

Test #2:

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

input:

1/3

output:

impossible

result:

ok 

Test #3:

score: -100
Wrong Answer
time: 2ms
memory: 4872kb

input:

7/4

output:

400 399
2 3
3 4
4 5
5 1
6 7
7 8
8 9
9 1
10 11
11 12
12 13
13 1
14 15
15 16
16 17
17 1
18 19
19 20
20 21
21 1
22 23
23 24
24 25
25 1
26 27
27 1
28 29
29 1
30 31
31 1
32 33
33 1
34 35
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 ...

result:

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