結果

問題 No.814 ジジ抜き
ユーザー leaf_1415
提出日時 2019-04-16 03:30:10
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 319 ms
コード長 617 Byte
コンパイル時間 273 ms
使用メモリ 8,916 KB
最終ジャッジ日時 2019-06-05 20:55:19

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0_sample1.txt AC 5 ms
6,868 KB
0_sample2.txt AC 3 ms
6,872 KB
0_sample3.txt AC 3 ms
6,868 KB
1_small1.txt AC 6 ms
6,872 KB
2_large1.txt AC 311 ms
8,916 KB
2_large2.txt AC 311 ms
8,548 KB
4_random1.txt AC 319 ms
8,512 KB
4_random2.txt AC 97 ms
6,868 KB
4_random3.txt AC 157 ms
8,460 KB
4_random4.txt AC 229 ms
7,500 KB
4_random5.txt AC 293 ms
8,436 KB
4_random6.txt AC 315 ms
8,464 KB
4_random7.txt AC 139 ms
6,872 KB
4_random8.txt AC 138 ms
6,868 KB
4_random9.txt AC 204 ms
7,648 KB
4_random10.txt AC 113 ms
6,868 KB
4_random11.txt AC 76 ms
6,872 KB
4_random12.txt AC 256 ms
7,848 KB
4_random13.txt AC 201 ms
7,296 KB
4_random14.txt AC 216 ms
8,472 KB
4_random15.txt AC 157 ms
6,868 KB
4_random16.txt AC 120 ms
6,920 KB
4_random17.txt AC 137 ms
7,940 KB
4_random18.txt AC 100 ms
6,868 KB
4_random19.txt AC 142 ms
7,504 KB
4_random20.txt AC 102 ms
6,956 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <iostream>
#define llint long long

using namespace std;

llint n;
llint k[300005], l[300005], d[300005];

bool check(llint x)
{
	llint ret = 0;
	for(int i = 1; i <= n; i++){
		if(x-l[i] < 0) continue;
		llint cnt = (x-l[i])/(1LL<<d[i])+1;
		if(cnt < 0) cnt = 0;
		if(cnt > k[i]) cnt = k[i];
		ret += cnt;
	}
	return ret % 2;
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> k[i] >> l[i] >> d[i];
	
	llint ub = 1e18+5, lb = -1, mid;
	while(ub-lb>1){
		mid=(ub+lb)/2;
		if(check(mid)) ub = mid;
		else lb = mid;
	}
	cout << ub << endl;
	
	return 0;
}
0