QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#360037 | #5154. ETA | kevinyang# | WA | 7ms | 10496kb | C++17 | 1.3kb | 2024-03-21 10:27:23 | 2024-03-21 10:27:23 |
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*=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