oj.uz

답안 #879619

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
879619 2023-11-27T18:22:32 Z Elvin_Fritl 홀-짝 수열 (IZhO11_oddeven) C++17
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define io                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
 
 
typedef long long ll;
 
ll bp(ll n,ll m){
    if(m == 0){
        return 1;
    }
    if(m == 1){
        return n;
    }
    if(m%2==0){
        return bp(n*n,m/2);
    }
    return n*bp(n,m-1);
}
 
 
const int N =  1e6 + 545, M = 33, inf = 1e9 + 99;
const ll inff = 1e12;

string sum(string a,string b) {
	string res;
	if((int)a.size() < (int)b.size()) {
		swap(a,b);
	}
	reverse(a.begin() , a.end());
	reverse(b.begin() , b.end());
	int tmp = 0;
	for(int i=0;i<(int)a.size();i++) {
		if((int)b.size() <= i) {
			res = res + char(((a[i] - '0') + tmp)%10 + '0');
			tmp = ((a[i] - '0') + tmp)/10;
		}
		else {
			res = res + char(((a[i] - '0') + tmp + (b[i] - '0')%10) + '0');
			tmp = ((a[i] - '0') + tmp + (b[i] - '0'))/10;
		}
	}
	if(tmp > 0) {
		res = res + char(tmp);
	}
	reverse(res.begin() , res.end());
	return res;
}

string div(string a) {
	string res;
	//reverse(a.begin() , a.end());
	int tmp = 0;
	for(int i=0;i<(int)a.size();i++) {
		if((tmp * 10 + (a[i] - '0'))/2 == 0) {
			tmp = (a[i] - '0');
			if(res.size() == 0) {
				continue;
			}
			res = res + '0';
		}
		else {
			int eded = (tmp * 10 + (a[i] - '0'))%2;
			string tt = to_string(((tmp * 10 + (a[i] - '0'))/2));
			res = res + tt;
			tmp = eded;
		}
	}
	return res;
}

string mul(string a, string b) {
    int m = a.size() , n = b.size();
    string res(m + n, '0');

    for(int i=m-1;i>=0;i--) {
        int tmp = 0;
        for(int j=n-1;j>=0;j--) {
            int cur = (a[i] - '0') * (b[j] - '0') + (res[i + j + 1] - '0') + tmp;
            res[i + j + 1] = cur % 10 + '0';
            tmp = cur / 10;
        }
        res[i] += tmp;
    }

    // Remove leading zeros
    size_t it = res.find_first_not_of('0');
    if (it != std::string::npos) {
        return res.substr(it);
    }

    return "0";
}

string sub(string a, string b) {
    int m = a.size() , n = b.size();
    string res(max(m, n), '0');

    int tmp = 0;
    for(int i=0;i<max(m, n);i++) {
        int fi = (i < m) ? (a[m - 1 - i] - '0') : 0 , se = (i < n) ? (b[n - 1 - i] - '0') : 0;

        int cur = fi - se - tmp;
        if(cur < 0) {
            cur += 10;
            tmp = 1;
        } 
        else {
            tmp = 0;
        }

        res[res.size() - 1 - i] = cur + '0';
    }

    // Remove leading zeros
    size_t it = res.find_first_not_of('0');
    if (it != std::string::npos) {
        return res.substr(it);
    }

    return "0"; 
}
 
int main() {
	
	
	string n;
	cin >> n;
    string l = "1" , r = n , res = "-1";
    while(l <= r) {
        string mid = div(sum(l , r));
        if(div(mul(mid , sum(mid , "1"))) >= n) {
			r = sub(mid , "1");
			res = mid;
		}
        else {
			l = sum(mid , "1");
		}
    }
    cout << sub(mul("2" , n) , res);
    
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -