oj.uz

Submission #373335

# Submission time Handle Problem Language Result Execution time Memory
373335 2021-03-04T07:11:37 Z koioi.org-moonrabbit2 Joyful KMP (KRIII5_JK) C++17
7 / 7
 262 ms 88352 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 l2;
//typedef long long l2;
typedef long double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int> tii;
typedef tuple<db,db,db> tdb;
typedef tuple<ll,ll,ll> tll;
typedef tuple<int,int,int,int> ti4;
typedef tuple<ll,ll,ll,ll> tl4;
typedef tuple<db,db,db,db> td4;
typedef vector<vector<ll>> mat;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //shuffle(a+1,a+1+n,rng)
uniform_int_distribution<> gen(1,100); //gen(rng)
//https://codeforces.com/contest/1264/submission/66344993 + 몇 가지 기능 직접 추가
ll modinv(ll a,ll m){
	if(m==1) return 0;
	a%=m;
	if(a<0) a+=m;
	if(a==1) return 1;
	return m-modinv(m,a)*m/a;
}
template <int MOD_> struct modnum{
private:
	int v;
public:
	static const int MOD = MOD_;
 
	modnum() : v(0) {}
	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
	explicit operator int () const { return v; }
	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
	friend bool operator < (const modnum& a, const modnum& b) { return a.v < b.v; }
	friend bool operator <= (const modnum& a, const modnum& b) { return a.v <= b.v; }
	friend bool operator > (const modnum& a, const modnum& b) { return a.v > b.v; }
	friend bool operator >= (const modnum& a, const modnum& b) { return a.v >= b.v; }
 
	modnum operator ~ () const {
		modnum res;
		res.v = modinv(v, MOD);
		return res;
	}
 
	modnum& operator += (const modnum& o) {
		v += o.v;
		if (v >= MOD) v -= MOD;
		return *this;
	}
	modnum& operator -= (const modnum& o) {
		v -= o.v;
		if (v < 0) v += MOD;
		return *this;
	}
	modnum& operator *= (const modnum& o) {
		v = int(ll(v) * ll(o.v) % MOD);
		return *this;
	}
	modnum& operator /= (const modnum& o) {
		return *this *= (~o);
	}
 
	
	modnum operator-() const { return modnum(-v); }
	modnum& operator++() { return *this += 1; }
	modnum operator++(int){ modnum tmp=*this; ++*this; return tmp; }
	modnum& operator--() { return *this -= 1; }
	modnum operator--(int){ modnum tmp=*this; --*this; return tmp; }
 
	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
	friend modnum pow(modnum a, ll p) {
		modnum ans = 1;
		for (; p; p /= 2, a *= a) if (p&1) ans *= a;
		return ans;
	}
	friend ostream& operator<<(std::ostream& os, const modnum& o)
	{
		os << o.v;
		return os;
	}
	friend istream& operator>>(std::istream& is, modnum& o)
	{
		is >> o.v;
		return is;
	}
};
const ll mod=1e9+7,inf=1e18;
using mi=modnum<1000000007>;
const int N=1e6+5,M=1e7+5;
string s;
int n,k,f[N],p[N],c[N],deg[N],m;
bool ok[30];
ll Q,sfx[N];
pii e[M];
mi ans=1;
vector<int> g[N];
int Find(int x){
    if(p[x]==x) return x;
    return p[x]=Find(p[x]);
}
void Union(int x,int y){
    x=Find(x); y=Find(y);
    if(x>y) swap(x,y);
    if(x<y) p[y]=x;
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>s>>Q;
    n=s.size(); s="$"+s;
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=2;i<=n;i++){
        while(k&&s[k+1]!=s[i]){
            e[++m]=pii(k+1,i); k=f[k];
        }
        assert(k<i);
        if(s[k+1]==s[i]){
            k++;
            Union(k,i);
        }
        else e[++m]=pii(k+1,i);
        f[i]=k;
    }
    for(int i=1;i<=m;i++){
        e[i]=pii(Find(e[i].fi),Find(e[i].se));
        if(e[i].fi>e[i].se) swap(e[i].fi,e[i].se);
    }
    sort(e+1,e+1+m); m=unique(e+1,e+1+m)-e-1;
    for(int i=1;i<=m;i++){
        g[e[i].se].emplace_back(e[i].fi);
        deg[e[i].se]++;
    }
    sfx[n+1]=1;
    for(int i=n;i>=1;i--){
        sfx[i]=sfx[i+1];
        if(Find(i)==i){
            ans*=26-deg[i];
            if(sfx[i]!=-1&&sfx[i]<=Q/(26-deg[i])) sfx[i]*=26-deg[i];
            else sfx[i]=-1;
        }
    }
    cout<<ans<<"\n";
    if(sfx[1]!=-1&&Q!=ans){
        cout<<"OVER"; return 0;
    }
    for(int i=1;i<=26;i++) ok[i]=1;
    for(int i=1;i<=n;i++) if(Find(i)==i){
        for(int j : g[i]) ok[c[j]]=0;
        ll ret=1;
        if(sfx[i+1]!=-1){
            for(int j=1;j<=26;j++) if(sfx[i+1]<Q){
                Q-=sfx[i+1];
                ret++;
            }
        }
        for(int j=1;j<=26;j++) if(ok[j]){
            ret--;
            if(!ret){
                c[i]=j;
                break;
            }
        }
        for(int j : g[i]) ok[c[j]]=1;
    }
    for(int i=1;i<=n;i++) cout<<(char)('a'+c[Find(i)]-1);
	return 0;
}

Subtask #1
7.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23916 KB Output is correct
2 Correct 17 ms 23916 KB Output is correct
3 Correct 16 ms 23916 KB Output is correct
4 Correct 18 ms 23916 KB Output is correct
5 Correct 229 ms 88224 KB Output is correct
6 Correct 262 ms 88256 KB Output is correct
7 Correct 225 ms 88352 KB Output is correct
8 Correct 258 ms 88224 KB Output is correct
9 Correct 235 ms 88240 KB Output is correct
10 Correct 16 ms 23916 KB Output is correct
11 Correct 17 ms 23916 KB Output is correct
12 Correct 17 ms 23916 KB Output is correct
13 Correct 18 ms 24172 KB Output is correct
14 Correct 19 ms 24300 KB Output is correct
15 Correct 26 ms 26220 KB Output is correct
16 Correct 36 ms 28392 KB Output is correct
17 Correct 115 ms 46600 KB Output is correct
18 Correct 215 ms 69152 KB Output is correct
19 Correct 220 ms 69024 KB Output is correct
20 Correct 212 ms 69280 KB Output is correct
21 Correct 210 ms 69280 KB Output is correct
22 Correct 197 ms 69600 KB Output is correct
23 Correct 73 ms 42656 KB Output is correct
24 Correct 71 ms 42784 KB Output is correct
25 Correct 72 ms 42656 KB Output is correct
26 Correct 72 ms 42784 KB Output is correct
27 Correct 72 ms 42656 KB Output is correct
28 Correct 72 ms 42656 KB Output is correct
29 Correct 71 ms 42696 KB Output is correct
30 Correct 78 ms 42740 KB Output is correct
31 Correct 71 ms 42784 KB Output is correct
32 Correct 71 ms 43040 KB Output is correct
33 Correct 71 ms 42656 KB Output is correct
34 Correct 71 ms 42656 KB Output is correct
35 Correct 70 ms 42656 KB Output is correct
36 Correct 71 ms 42784 KB Output is correct
37 Correct 71 ms 42784 KB Output is correct
38 Correct 70 ms 42656 KB Output is correct
39 Correct 71 ms 42912 KB Output is correct
40 Correct 73 ms 42784 KB Output is correct
41 Correct 71 ms 42656 KB Output is correct
42 Correct 72 ms 42656 KB Output is correct
43 Correct 71 ms 42784 KB Output is correct
44 Correct 70 ms 42656 KB Output is correct
45 Correct 73 ms 42656 KB Output is correct
46 Correct 72 ms 42668 KB Output is correct
47 Correct 72 ms 42656 KB Output is correct
48 Correct 72 ms 42656 KB Output is correct
49 Correct 36 ms 41632 KB Output is correct
50 Correct 74 ms 42748 KB Output is correct