Submission #258564

#	Time	Username	Problem	Language	Result	Execution time	Memory
258564		errorgorn	Devil's Share (RMI19_devil)	C++14	0 / 100	1588 ms	3704 KiB

devil

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

mt19937 rng(186608); //this is cursed

const int MOD=1000000007;
const ll P=173;
const ll invP=791907520;

ll powp[100005];
ll invp[100005];

ll base[10];

ll fix(ll i){
	i%=MOD;
	if (i<0) i+=MOD;
	
	return i;
}

int n,k;
int arr[10]; //dont change this
int cnt[10];

int ans[100005];
int goal[100005];

int h1[100005];
int h2[100005];

bool can(){
	rep(x,1,10) cnt[x]=arr[x];
	
	rep(x,1,k+1){
		h2[x]=(h2[x-1]+base[goal[x]]*powp[x])%MOD;
	}
	
	rep(x,1,n+1){
		rep(digit,10,0){
			if (digit==0) return false;
			if (cnt[digit]==0) continue;
			
			ans[x]=digit;
			h1[x]=(h1[x-1]+base[digit]*powp[x])%MOD;
			
			if (x<k || digit<goal[k]){
				cnt[digit]--;
				break;
			}
			
			int lo=0,hi=k+1,mi;
			while (hi-lo>1){
				mi=hi+lo>>1;
				
				if (fix(h2[k]-h2[k-mi])*invp[k-mi]%MOD==fix(h1[x]-h1[x-mi])*invp[x-mi]%MOD){
					lo=mi;
				}
				else{
					hi=mi;
				}
			}
			
			if (ans[x-lo]<goal[k-lo]){
				cnt[digit]--;
				break;
			}
		}
	}
	
	return true;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	powp[0]=invp[0]=1;
	rep(x,1,100005){
		powp[x]=(powp[x-1]*P)%MOD;
		invp[x]=(invp[x-1]*invP)%MOD;
	}
	
	rep(x,0,10) base[x]=rng()%MOD;
	
	int TC;
	cin>>TC;
	while (TC--){
		cin>>k;
		n=0;
		rep(x,1,10){
			cin>>arr[x];
			n+=arr[x];
		}
		
		goal[0]=10; //zzz
		rep(x,1,k+1) goal[x]=9;
		
		rep(x,k+1,1){
			rep(digit,9,1){
				goal[x]=digit;
				if (!can()){
					goal[x]=digit+1;
					break;
				}
			}
		}
		
		rep(x,n+1,1) cout<<ans[x]; cout<<endl;
	}
}

Compilation message (stderr)

devil.cpp: In function 'bool can()':
devil.cpp:82:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     mi=hi+lo>>1;
        ~~^~~
devil.cpp: In function 'int main()':
devil.cpp:19:26: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
                          ^
devil.cpp:138:3: note: in expansion of macro 'rep'
   rep(x,n+1,1) cout<<ans[x]; cout<<endl;
   ^~~
devil.cpp:138:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   rep(x,n+1,1) cout<<ans[x]; cout<<endl;
                              ^~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 29
• Subtask 4: 0 / 44