QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#91241 | #1900. Octopus Game | rania__ | WA | 2ms | 3468kb | C++14 | 2.7kb | 2023-03-27 20:52:31 | 2023-03-27 20:52:32 |
Judging History
answer
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 5e5 + 7, P1 = 31, P2 = 37, mod = 1e9 + 7;
void fractionToDecimal(int numr, int denr)
{
string res; // Initialize result
// Create a map to store already
// seen remainders, remainder is used
// as key and its position in
// result is stored as value.
// Note that we need
// position for cases like 1/6.
// In this case,the recurring sequence
// doesn't start from first
// remainder.
map<int, int> mp;
mp.clear();
// Find first remainder
int rem = numr % denr;
// Keep finding remainder until either remainder
// becomes 0 or repeats
int cnt =0;
while ((rem != 0)
&& (mp.find(rem) == mp.end()))
{
// Store this remainder
mp[rem] = res.length();
// Multiply remainder with 10
rem = rem * 10;
// Append rem / denr to result
int res_part = rem / denr;
res += to_string(res_part);
// Update remainder
cnt++;
rem = rem % denr;
}
if (rem == 0)
{
cout << cnt << " " << 0 << endl;
}
else
cout << cnt-res.substr(mp[rem]).size() << " " << res.substr(mp[rem]).size() << endl;
}
void doWork() {
int x,y;
cin >> x >> y;
vector<pair<int,int>> ans;
while(x && y)
{
if(abs(x) > abs(y))
{
int cur = x / y;
if(abs(x - (cur + 1) * y) < abs(x - cur * y))
++cur;
if(abs(x - (cur - 1) * y) < abs(x - cur * y))
--cur;
x -= cur * y;
ans.push_back({1,-cur});
}
else
{
swap(x,y);
int cur = x / y;
if(abs(x - (cur + 1) * y) < abs(x - cur * y))
++cur;
if(abs(x - (cur - 1) * y) < abs(x - cur * y))
--cur;
x -= cur * y;
swap(x,y);
ans.push_back({2,-cur});
}
}
cout << ans.size() << endl;
for(auto it : ans)
cout << it.first << " " << it.second << endl;
}
int main() {
ios::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
// freopen("bisector.in","r",stdin);
// freopen("bisector.out","w",stdout);
int t = 1;
// cout << primes.size() << endl;
//cin >> t;
while (t--) {
doWork();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3344kb
input:
-3 9
output:
1 2 3
result:
ok heap reached 0 count in less than 50 steps
Test #2:
score: 0
Accepted
time: 2ms
memory: 3400kb
input:
-27 57
output:
2 2 2 1 9
result:
ok heap reached 0 count in less than 50 steps
Test #3:
score: 0
Accepted
time: 2ms
memory: 3364kb
input:
56 15
output:
3 1 -4 2 4 1 -4
result:
ok heap reached 0 count in less than 50 steps
Test #4:
score: 0
Accepted
time: 0ms
memory: 3360kb
input:
6 -2
output:
1 1 3
result:
ok heap reached 0 count in less than 50 steps
Test #5:
score: 0
Accepted
time: 2ms
memory: 3380kb
input:
-84 57
output:
3 1 1 2 2 1 9
result:
ok heap reached 0 count in less than 50 steps
Test #6:
score: 0
Accepted
time: 0ms
memory: 3356kb
input:
-648 -315
output:
3 1 -2 2 -17 1 -2
result:
ok heap reached 0 count in less than 50 steps
Test #7:
score: 0
Accepted
time: 0ms
memory: 3360kb
input:
4418 -527
output:
6 1 8 2 3 1 -3 2 2 1 4 2 -9
result:
ok heap reached 0 count in less than 50 steps
Test #8:
score: 0
Accepted
time: 2ms
memory: 3360kb
input:
55796 83094
output:
6 2 -1 1 -2 2 -23 1 4 2 -38 1 4
result:
ok heap reached 0 count in less than 50 steps
Test #9:
score: 0
Accepted
time: 2ms
memory: 3352kb
input:
581706 382159
output:
10 1 -2 2 2 1 11 2 -5 1 3 2 -2 1 -3 2 -7 1 4 2 7
result:
ok heap reached 0 count in less than 50 steps
Test #10:
score: 0
Accepted
time: 2ms
memory: 3412kb
input:
-1570717 -5452307
output:
12 2 -3 1 -2 2 -8 1 -5 2 -3 1 10 2 2 1 3 2 -3 1 5 2 -2 1 -3
result:
ok heap reached 0 count in less than 50 steps
Test #11:
score: 0
Accepted
time: 2ms
memory: 3468kb
input:
35296299 62120456
output:
10 2 -2 1 4 2 6 1 55 2 -3 1 11 2 5 1 3 2 -10 1 -5
result:
ok heap reached 0 count in less than 50 steps
Test #12:
score: 0
Accepted
time: 2ms
memory: 3368kb
input:
133453354 276321715
output:
12 2 -2 1 -14 2 -6 1 4 2 -3 1 -3 2 -3 1 3 2 -20 1 5 2 7 1 7
result:
ok heap reached 0 count in less than 50 steps
Test #13:
score: -100
Wrong Answer
time: 2ms
memory: 3388kb
input:
4087302427 739712346
output:
6 1 -65797 2 -28 1 -9 2 14 1 2 2 4
result:
wrong answer absolute count of balls in the heaps must be less than 1000000000000000000