oj.uz

답안 #764496

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
764496 2023-06-23T13:19:14 Z Trunkty 홀-짝 수열 (IZhO11_oddeven) C++14
0 / 100
 3 ms 332 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

struct bigint{
    vector<int> v={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
};

int mod = 1e9;

bigint add(bigint a, bigint b){
    bigint c;
    for(int i=0;i<=30;i++){
        c.v[i] = a.v[i]+b.v[i];
        if(c.v[i]>mod){
            c.v[i] -= mod;
            c.v[i+1]++;
        }
    }
    return c;
}

bigint sub(bigint a, bigint b){
    bigint c;
    for(int i=0;i<=30;i++){
        c.v[i] = a.v[i]-b.v[i];
        if(c.v[i]<0){
            c.v[i] += mod;
            a.v[i+1]--;
        }
    }
    return c;
}

bigint mult(bigint a, bigint b){
    bigint c;
    for(int i=0;i<=30;i++){
        for(int j=0;j<=30;j++){
            if(i+j<=30){
                c.v[i+j] += a.v[i]*b.v[j];
                c.v[i+j+1] += c.v[i+j]/mod;
                c.v[i+j] %= mod;
            }
        }
    }
    return c;
}

bool bigeq(bigint a, bigint b){
    for(int i=30;i>=0;i--){
        if(a.v[i]>b.v[i]){
            return true;
        }
        else if(a.v[i]<b.v[i]){
            return false;
        }
    }
    return true;
}

string s;
bigint n,one,two;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    one.v[0] = 1;
    two.v[0] = 2;
    cin >> s;
    reverse(s.begin(),s.end());
    for(int i=s.length()-1;i>=0;i--){
        n.v[i/9] *= 10LL;
        n.v[i/9] += s[i]-'0';
    }
    n = mult(n,two);
    bigint tosub;
    for(int j=15;j>=0;j--){
        int low=0,high=mod-1;
        while(low!=high){
            int mid = (low+high+1)/2;
            tosub.v[j] = mid;
            if(bigeq(mult(tosub,add(tosub,one)),n)){
                high = mid-1;
            }
            else{
                low = mid;
            }
        }
        tosub.v[j] = low;
    }
    tosub = add(tosub,one);
    n = sub(n,tosub);
    for(int i=30;i>=0;i--){
        if(n.v[i]>0){
            cout << n.v[i];
        }
    }
    cout << "\n";
    return 0;
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 212 KB Output is correct
2 Correct 3 ms 212 KB Output is correct
3 Correct 3 ms 328 KB Output is correct
4 Correct 3 ms 212 KB Output is correct
5 Correct 3 ms 320 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Incorrect 3 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -