QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#360021 | #5154. ETA | kevinyang# | WA | 2ms | 4872kb | C++17 | 1.5kb | 2024-03-21 10:00:16 | 2024-03-21 10:00:16 |
Judging History
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