結果

問題 No.262 面白くないビットすごろく
ユーザー kurenaifkurenaif
提出日時 2016-02-26 22:18:52
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 468 ms / 2,000 ms
コード長 2,524 bytes
コンパイル時間 622 ms
コンパイル使用メモリ 70,528 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-22 14:03:41
合計ジャッジ時間 3,287 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 459 ms
6,812 KB
testcase_01 AC 468 ms
6,940 KB
testcase_02 AC 468 ms
6,944 KB
testcase_03 AC 467 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <queue>
#include <map>
#include <list>
#include <vector>
#include <string>
#include <limits>
#include <cassert>
#include <fstream>
#include <cstring>

using namespace std;

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)

#define inf INT_MAX/3
#define INF INT_MAX/3
#define PB push_back
#define MP make_pair
#define ALL(a) (a).begin(),(a).end()
#define SET(a,c) memset(a,c,sizeof a)
#define CLR(a) memset(a,0,sizeof a)
#define pii pair<int,int>
#define pcc pair<char,char>
#define pic pair<int,char>
#define pci pair<char,int>
#define VS vector<string>
#define VI vector<int>
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define MIN(a,b) (a>b?b:a)
#define MAX(a,b) (a>b?a:b)
#define pi 2*acos(0.0)
#define INFILE() freopen("in0.txt","r",stdin)
#define OUTFILE()freopen("out0.txt","w",stdout)
#define in scanf
#define out printf
#define ll long long
#define ull unsigned long long
#define eps 1e-14
#define FST first
#define SEC second

ll popcnt(ll bits)
{
	return __builtin_popcountll(bits);
}

//解説読みました…
//最大値的には, 全体で40bit
//方針としては, 下位20bitと, 上位20bitを分け, 20bitずつ一気に進めて, 最後に調整する感じ
//上位20bitはoffsetみたいな感じで扱う

ll add[42][42];//add[上位20bitの数][繰り上がるまで進んで余ってちょっと進んだ分]:次はどこに行くのか
ll cnt[42][42];//cnt[same][same]:次に行くところまでにかかった回数

int main(void) {
	ll N; cin >> N;

	REP(i, 42) REP(j, 42) {
		if (i == 0 && i == j) continue; //0だと完全に詰まるのでダメ
		ll cur = j;
		ll c = 0;
		while (cur < (1 << 20)) { //次の繰り上げが発生するまで数え上げをする
			cur += popcnt(cur) + i; //進む量は下位20bit+上位のpopcnt
			++c;
		}
		add[i][j] = cur - j;
		cnt[i][j] = c;
	}

	ll cur = 1;
	ll res = 1;//最初は1スタート

	while (1) {
		//(あまりは40までなので, 2^20で割る必要はなくて, 40以上で2の倍数の64で割る 配列にはみ出しそうだけどはみ出さない だ、大丈夫だから(震え声))
		ll next = cur + add[popcnt(cur >> 20)][cur % 64];
		if (next >= N) break; //行き過ぎた
		res += cnt[popcnt(cur >> 20)][cur % 64];
		cur = next;
	}

	while (cur < N) {
		cur += popcnt(cur);
		++res;
	}

	if (cur == N) cout << res << endl;
	else cout << -1 << endl;

	return 0;
}
0