結果

問題 No.262 面白くないビットすごろく
コンテスト
ユーザー wwwyq07
提出日時 2025-10-14 14:45:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,157 bytes
コンパイル時間 1,997 ms
コンパイル使用メモリ 196,032 KB
実行使用メモリ 15,948 KB
最終ジャッジ日時 2025-10-14 14:45:47
合計ジャッジ時間 6,154 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 1 OLE * 1 -- * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘Node F(int, int, int)’:
main.cpp:17:44: warning: narrowing conversion of ‘(((ll)((p + __builtin_popcount(((unsigned int)p))) + v)) - pw[t])’ from ‘ll’ {aka ‘long long int’} to ‘int’ [-Wnarrowing]
   17 |         return {1,p+__builtin_popcount(p)+v-pw[t]};
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
main.cpp: In function ‘int main()’:
main.cpp:26:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   26 |     scanf("%d",&T);
      |     ~~~~~^~~~~~~~~
main.cpp:31:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   31 |         scanf("%lld",&n);
      |         ~~~~~^~~~~~~~~~~

ソースコード

diff # 

/*
你能不能进省队？
初志贯彻！
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,now,cnt;
ll n,pw[63],ans;
struct Node{
    ll c;
    int t;
}f[63][63][63],res;
bool vis[63][63][63];
inline Node F(int p,int v,int t){
    if(p+__builtin_popcount(p)+v>=pw[t])
        return {1,p+__builtin_popcount(p)+v-pw[t]};
    if(vis[p][v][t])
        return f[p][v][t];
    vis[p][v][t]=1;
    f[p][v][t]=F(p,v,t-1);
    res=F(f[p][v][t].t,v+1,t-1);
    return f[p][v][t]={f[p][v][t].c+res.c,res.t};
}
int main(){
    scanf("%d",&T);
    pw[0]=1;
    for(int i=1;i<63;i++)
        pw[i]=pw[i-1]<<1;
    while(T--){
        scanf("%lld",&n);
        now=1;ans=cnt=0;
        for(int i=62;~i;i--)
            if(n&pw[i]){
                if(now>=pw[i])
                    now-=pw[i];
                else{
                    res=F(now,cnt,i);
                    // printf("%d %d %d\n",i,res.c,res.t);
                    ans+=res.c;
                    now=res.t;
                }
                cnt++;
            }
        if(now)
            puts("-1");
        else
            printf("%lld\n",ans-1);
    }
    return 0;
}
0