| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 548267 | racsosabe | Odd-even (IZhO11_oddeven) | C++14 | 3 ms | 468 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace::std;
struct BigInteger{
vector<int> v;
BigInteger(){
v.emplace_back(0);
}
BigInteger(int x){
if(x == 0){
v.emplace_back(0);
return;
}
while(x){
v.emplace_back(x % 10);
x /= 10;
}
}
BigInteger(vector<int> &v){
this -> v = v;
}
BigInteger(string s){
for(int i = s.size() - 1; i >= 0; i--){
v.emplace_back(s[i] - '0');
}
}
BigInteger operator + (const BigInteger b){
vector<int> res(max(v.size(), b.v.size()));
for(int i = 0; i < res.size(); i++){
if(i < v.size()) res[i] += v[i];
if(i < b.v.size()) res[i] += b.v[i];
}
for(int i = 0; i < res.size(); i++){
if(res[i] >= 10){
if(i + 1 < res.size()) res[i + 1] += res[i] / 10;
else res.emplace_back(res[i] / 10);
res[i] %= 10;
}
}
return BigInteger(res);
}
BigInteger operator * (const BigInteger b){
vector<int> res(v.size() + b.v.size());
for(int i = 0; i < v.size(); i++){
for(int j = 0; j < b.v.size(); j++){
res[i + j] += v[i] * b.v[j];
}
}
for(int i = 0; i < res.size(); i++){
if(res[i] >= 10){
if(i + 1 < res.size()) res[i + 1] += res[i] / 10;
else res.emplace_back(res[i] / 10);
res[i] %= 10;
}
}
while(res.size() > 1 and res.back() == 0) res.pop_back();
return BigInteger(res);
}
BigInteger operator - (const BigInteger b){
vector<int> res(max(v.size(), b.v.size()));
for(int i = 0; i < res.size(); i++){
if(i < v.size()) res[i] += v[i];
if(i < b.v.size()) res[i] -= b.v[i];
}
for(int i = 0; i < res.size(); i++){
if(res[i] < 0){
res[i] += 10;
res[i + 1] -= 1;
}
}
while(res.size() > 1 and res.back() == 0) res.pop_back();
return BigInteger(res);
}
bool operator < (const BigInteger b){
if(v.size() == b.v.size()){
for(int i = v.size() - 1; i >= 0; i--){
if(v[i] != b.v[i]) return v[i] < b.v[i];
}
return false;
}
return v.size() < b.v.size();
}
bool operator <= (const BigInteger b){
if(v.size() == b.v.size()){
for(int i = v.size() - 1; i >= 0; i--){
if(v[i] != b.v[i]) return v[i] < b.v[i];
}
return true;
}
return v.size() < b.v.size();
}
void half(){
for(int i = v.size() - 1; i >= 0; i--){
if(v[i] & 1) v[i - 1] += 10;
v[i] /= 2;
}
while(v.size() > 1 and v.back() == 0) v.pop_back();
}
void print(){
for(int i = v.size() - 1; i >= 0; i--) cout << char('0' + v[i]);
cout << endl;
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
string s;
cin >> s;
BigInteger rt;
BigInteger n(s);
vector<BigInteger> pot;
pot.emplace_back(BigInteger("1"));
while(pot.back() <= n){
pot.emplace_back(pot.back() + pot.back());
}
for(int i = pot.size() - 1; i >= 0; i--){
BigInteger new_value = (rt + pot[i]) * (rt + pot[i] + pot[0]);
new_value.half();
if(new_value < n){
rt = rt + pot[i];
}
}
BigInteger at = pot[1] * n - rt - pot[0];
at.print();
return 0;
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||