oj.uz

Submission #42346

# Submission time Handle Problem Language Result Execution time Memory
42346 2018-02-26T09:06:16 Z milmillin Poklon (COCI17_poklon7) C++14
120 / 120
 375 ms 72092 KB 
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int l[1000100];
int r[1000100];

struct bigInt {
	unsigned int a;
	int p;

	bigInt ex() const {
		return bigInt{a,p+1};
	}
};

bool operator< (const bigInt &a, const bigInt &b) {
	if (a.p<b.p) return !(b<a);
	if (a.p==b.p) return a.a<b.a;
	for (int i=31;i>max(31-(a.p-b.p),0);i--) {
		if ((1<<i)&a.a) return false;
	}
	unsigned int tmp = a.a << (a.p-b.p);
	return tmp < b.a;
}

bigInt getWgt(int idx) {
	if (idx<0) return bigInt{(unsigned int)(-idx),0};
	return max(getWgt(l[idx]),getWgt(r[idx])).ex();
}

int main () {
	int n;
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {
		scanf("%d%d",&l[i],&r[i]);
	}
	auto tt=getWgt(1);
	//printf("%lld\n",ans);
	int ans=tt.a;
	string x;
	while (ans) {
		if (ans%2) x.push_back('1');
		else x.push_back('0');
		ans/=2;
	}
	reverse(x.begin(),x.end());
	cout << x;
	for (int i=0;i<tt.p;i++) {
		printf("0");
	}
	printf("\n");
	return 0;
}

Compilation message

poklon.cpp: In function 'int main()':
poklon.cpp:37:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
poklon.cpp:39:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&l[i],&r[i]);
                            ^

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 1 ms 432 KB Output is correct
4 Correct 1 ms 508 KB Output is correct
5 Correct 1 ms 528 KB Output is correct
6 Correct 1 ms 528 KB Output is correct
7 Correct 1 ms 528 KB Output is correct
8 Correct 1 ms 532 KB Output is correct
9 Correct 2 ms 532 KB Output is correct
10 Correct 2 ms 532 KB Output is correct
11 Correct 5 ms 820 KB Output is correct
12 Correct 6 ms 820 KB Output is correct
13 Correct 20 ms 2488 KB Output is correct
14 Correct 46 ms 4676 KB Output is correct
15 Correct 35 ms 4676 KB Output is correct
16 Correct 123 ms 11148 KB Output is correct
17 Correct 295 ms 23080 KB Output is correct
18 Correct 307 ms 26020 KB Output is correct
19 Correct 360 ms 26020 KB Output is correct
20 Correct 375 ms 72092 KB Output is correct