//雪花飄飄北風嘯嘯
//天地一片蒼茫
#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
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;
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
1920 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
305 ms |
3704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1588 ms |
2872 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
1920 KB |
Output isn't correct |
