#691260 (C++17) No.1651 Removing Cards

• 問題: No.1651 Removing Cards
• ユーザー: 沙耶花
• 提出日時: 2021-08-20 22:27:43
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 600 ms / 2,000 ms
• コード長: 1,150 bytes
• コンパイル時間: 4,110 ms
• コンパイル使用メモリ: 262,768 KB
• 実行使用メモリ: 7,504 KB
• 最終ジャッジ日時: 2024-10-14 04:23:18
• 合計ジャッジ時間: 17,643 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	124 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	2 ms; 5,248 KB
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	2 ms; 5,248 KB
testcase_07	AC	2 ms; 5,248 KB
testcase_08	AC	2 ms; 5,248 KB
testcase_09	AC	192 ms; 5,248 KB
testcase_10	AC	190 ms; 5,248 KB
testcase_11	AC	193 ms; 5,248 KB
testcase_12	AC	194 ms; 5,248 KB
testcase_13	AC	192 ms; 5,248 KB
testcase_14	AC	194 ms; 5,248 KB
testcase_15	AC	574 ms; 7,500 KB
testcase_16	AC	564 ms; 7,500 KB
testcase_17	AC	578 ms; 7,500 KB
testcase_18	AC	565 ms; 7,428 KB
testcase_19	AC	569 ms; 7,500 KB
testcase_20	AC	560 ms; 7,496 KB
testcase_21	AC	564 ms; 7,500 KB
testcase_22	AC	577 ms; 7,496 KB
testcase_23	AC	196 ms; 5,248 KB
testcase_24	AC	156 ms; 5,248 KB
testcase_25	AC	539 ms; 7,500 KB
testcase_26	AC	513 ms; 7,500 KB
testcase_27	AC	600 ms; 7,504 KB
testcase_28	AC	586 ms; 7,376 KB
testcase_29	AC	581 ms; 7,504 KB
testcase_30	AC	582 ms; 7,500 KB
testcase_31	AC	584 ms; 7,496 KB
testcase_32	AC	173 ms; 5,248 KB
testcase_33	AC	177 ms; 5,248 KB
testcase_34	AC	174 ms; 5,248 KB

ソースコード

#include <stdio.h>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf 1000000000000000001


int main(){
	
	long long K,Q;
	cin>>K>>Q;
	
	vector<long long> S(1,0);
	S.push_back(1);
	
	while(true){
		long long aa = S[S.size()-2];
		long long ok = Inf,ng = S.back();
		while(ok-ng>1LL){
			long long mid = (ok+ng)/2;
			
			long long t = (mid-1)/K;
			t++;
			if(mid-t>=S.back())ok = mid;
			else ng = mid;
		}
		//if(S.back()==3)cout<<aa<<','<<ok<<endl;
		S.push_back(ok);
		if(S.back()>=Inf)break;
		
	}
	/*
	vector<long long> pos(S.size(),0);
	pos[1] = 1;
	
	for(int i=2;i<S.size();i++){
		long long t = pos[i-1];
		long long ok = Inf,ng = t;
		while(ok-ng>1LL){
			long long mid = (ok+ng)/2;
			long long tt = (mid-1)/K;
			tt++;
			if(mid-tt>=t)ok = mid;
			else ng = mid;
		}
		if((ok-1)%K==0)ok++;
		pos[i] = ok;
	}
	*/
	/*
	rep(i,10){
		cout<<S[i]<<endl;
	}*/
	
	
	
	rep(_,Q){
		long long N;
		cin>>N;
		
		int d = distance(S.begin(),upper_bound(S.begin(),S.end(),N));
		d--;
		cout<<S[d]<<endl;
	}
	
	return 0;
}