結果

問題 No.262 面白くないビットすごろく
ユーザー chocoruskchocorusk
提出日時 2018-12-08 07:28:20
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 583 ms / 2,000 ms
コード長 1,435 bytes
コンパイル時間 739 ms
コンパイル使用メモリ 94,636 KB
実行使用メモリ 179,584 KB
最終ジャッジ日時 2024-09-14 04:22:59
合計ジャッジ時間 3,770 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 372 ms
179,456 KB
testcase_01 AC 577 ms
179,584 KB
testcase_02 AC 583 ms
179,456 KB
testcase_03 AC 577 ms
179,456 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
	int c[1<<20], a[21][1<<20], b[21][1<<20];
	for(int i=0; i<(1<<20); i++){
		int i0=i; c[i]=0;
		while(i0){
			c[i]+=(i0&1); i0>>=1;
		}
	}
	for(int i=(1<<20)-1; i>=0; i--){
		for(int j=0; j<=20; j++){
			if(i==0 && j==0) continue;
			if(i+j+c[i]>=(1<<20)){
				a[j][i]=(i+j+c[i])&((1<<20)-1);
				b[j][i]=1;
			}else{
				a[j][i]=a[j][i+j+c[i]];
				b[j][i]=b[j][i+j+c[i]]+1;
			}
		}
	}
	ll n;
	cin>>n;
	ll x1=0, x2=1e12;
	while(x1!=x2){
		ll x0=(x1+x2+1)/2;
		ll x=x0;
		ll n0=1;
		ll i1=-1;
		for(int i=0; i<(1<<20); i++){
			if(x<b[c[i]][n0]){
				i1=i;
				break;
			}
			x-=b[c[i]][n0];
			n0=a[c[i]][n0];
		}
		if(i1==-1){
			x2=x0-1;
			continue;
		}
		for(int i=0; i<x; i++){
			n0+=(c[i1]+c[n0]);
		}
		if(i1*(1ll<<20)+n0<=n) x1=x0;
		else x2=x0-1;
	}
	ll ans=x1+1;
	ll n0=1;
	ll i1=-1;
	for(int i=0; i<(1<<20); i++){
		if(x1<b[c[i]][n0]){
			i1=i;
			break;
		}
		x1-=b[c[i]][n0];
		n0=a[c[i]][n0];
	}
	for(int i=0; i<x1; i++){
		n0+=(c[i1]+c[n0]);
	}
	if(i1*(1ll<<20)+n0==n){
		cout<<ans<<endl;
	}else{
		cout<<-1<<endl;
	}
	return 0;
}
0