QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#360035 | #5154. ETA | kevinyang# | WA | 4ms | 10412kb | C++17 | 1.3kb | 2024-03-21 10:26:18 | 2024-03-21 10:26:18 |
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';
}
//cout << sum << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3576kb
input:
1/2
output:
2 1 1 2
result:
ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
1/3
output:
impossible
result:
ok
Test #3:
score: -100
Wrong Answer
time: 4ms
memory: 10412kb
input:
7/4
output:
386 24 4 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...
result:
wrong answer Integer parameter [name=y] equals to 100000, violates the range [1, 386]