Submission #4863

#	Time	Username	Problem	Language	Result	Execution time	Memory
4863		tncks0121	Odd-even (IZhO11_oddeven)	C++98	100 / 100	16 ms	1124 KiB

oddeven

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <memory.h> 
#include <math.h> 
#include <assert.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <string> 
#include <functional> 
#include <vector> 
#include <deque> 
#include <utility> 
#include <bitset> 
#include <limits.h>  
#include <time.h>

using namespace std; 
typedef long long ll; 
typedef unsigned long long llu; 
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

const int SZ = 200;
int tmp[SZ];

struct bigint {
	char digit[SZ];

	bigint() { memset(digit, 0, sizeof digit); }
	bigint(int v) {
		memset(digit, 0, sizeof digit);
		int x = 0;
		while(v > 0) digit[x++] = v % 10, v /= 10;
	}

	void add (const bigint t) {
		for(int i = 0; i < SZ; i++) {
			digit[i] += t.digit[i];
			if(digit[i] >= 10) {
				digit[i+1] += digit[i]/10;
				digit[i] %= 10;
			}
		}
	}

	void sub (const bigint t) {
		for(int i = 0; i < SZ; i++) {
			digit[i] -= t.digit[i];
			while(digit[i] < 0) {
				digit[i+1]--;
				digit[i] += 10;
			}
		}
	}

	void mul (const bigint t) {
		for(int i = 0; i < SZ; i++) tmp[i] = digit[i], digit[i] = 0;
		for(int i = 0; i < SZ; i++) {
			for(int j = 0; j < SZ-i; j++) {
				digit[i+j] += (int)tmp[i] * (int)t.digit[j];
				if(digit[i+j] >= 10 && i+j+1 < SZ) {
					digit[i+j+1] += digit[i+j] / 10;
					digit[i+j] %= 10;
				}
			}
		}
	}

	bool operator<= (const bigint t) const {
		for(int i = SZ-1; i >= 0; i--) {
			char a = digit[i];
			char b = t.digit[i];
			if(a != b) return a < b;
		}
		return true;
	}
};

bigint N;
char D[105]; int DN;
bigint pow2[170];

int main() {
	int i, j, k;

	scanf("%s", D); DN = strlen(D);
	for(i = 0; i < DN; i++) N.digit[i] = D[DN-i-1] - '0';
	N.mul(2);

	if(!strcmp(D, "1")) return 0 & puts("1");

	pow2[0].digit[0] = 1;
	for(i = 1; i < 170; i++) {
		pow2[i] = pow2[i-1];
		pow2[i].mul(2);
	}

	bigint block;
	for(k = 169; k >= 0; k--) {
		bigint now;
		now = block; now.add(pow2[k]);

		bigint val = now;
		val.mul(now);
		val.add(now);

		if(val <= N) {
			block = now;
		}
	}

	bigint pre;
	pre.add(block);
	pre.mul(block);
	pre.add(block);
	
	bigint res;
	res.add(block);
	res.mul(block);
	res.add(N);
	res.sub(pre);
	res.sub(1);

	bool chk = false;
	for(k = SZ-1; k >= 0; k--) {
		if(res.digit[k] != 0) chk = true;
		if(chk) putchar(res.digit[k] + '0');
	}

	return 0;
}

• Subtask 1: 100 / 100