Submission #1688510
Source Code Expand
#include<set>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<complex>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1e18
using namespace std;
const int maxn = 210000;
ll L,R;
int n,pos;
bool flag;
int ex[maxn],id,mx;
char str[maxn];
struct node
{
ll n,s[26];
node(){n=0;memset(s,0,sizeof s);}
}f[maxn]; int ed;
inline node operator +(node &x,node &y)
{
node re; re.n=x.n+y.n;
for(int i=0;i<26;i++) re.s[i]=x.s[i]+y.s[i];
return re;
}
void dp()
{
f[0].n=pos;
for(int i=0;i<pos;i++) f[0].s[str[i]-'a']++;
f[1].n=n;
for(int i=0;i<n;i++) f[1].s[str[i]-'a']++;
ed=1;
while(f[ed].n<inf)
f[ed+1]=f[ed]+f[ed-1],ed++;
}
node solve1(ll x)
{
ll div=x/f[0].n,oth=x%f[0].n;
node re; for(int i=0;i<26;i++) re.s[i]=f[0].s[i]*div;
if(oth)
{
for(int i=0;i<oth;i++) re.s[str[i]-'a']++;
}
return re;
}
node solve2(ll x,int now)
{
while(now&&f[now-1].n>=x) now--;
node re;
if(now<=1)
{
for(int i=0;i<x;i++) re.s[str[i]-'a']++;
return re;
}
re=f[now-1];
node temp=solve2(x-f[now-1].n,now-2);
re=re+temp;
return re;
}
node calc(ll x)
{
node re;
if(!x) return re;
if(flag) re=solve1(x);
else re=solve2(x,ed);
}
int main()
{
scanf("%s",str); n=strlen(str); n>>=1; str[n]='$';
id=1,mx=0;
for(int i=1;i<n;i++)
{
if(mx>=i) ex[i]=min(ex[i-id],mx-i);
while(str[i+ex[i]]==str[ex[i]]) ex[i]++;
if(i+ex[i]-1>mx) id=i,mx=i+ex[i]-1;
}
flag=false;
for(pos=1;pos<n&&pos+ex[pos]-1!=n-1;pos++);
if(n%pos==0) flag=true;
dp();
scanf("%lld%lld",&L,&R);
node a1=calc(R),a2=calc(L-1);
for(int i=0;i<26;i++) printf("%lld ",a1.s[i]-a2.s[i]);
return 0;
}
Submission Info
Submission Time |
|
Task |
F - SS |
User |
lichangdongtw |
Language |
C++14 (GCC 5.4.1) |
Score |
1100 |
Code Size |
1888 Byte |
Status |
AC |
Exec Time |
17 ms |
Memory |
45312 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:86:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",str); n=strlen(str); n>>=1; str[n]='$';
^
./Main.cpp:100:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&L,&R);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1100 / 1100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample1.txt, sample2.txt, sample3.txt |
All |
mx_100000_1_0.txt, rnd_6_16666_4.txt, rnd_7777_1_0.txt, rnd_7777_1_2289.txt, rnd_7777_1_6444.txt, rnd_7777_9_0.txt, rnd_7777_9_1542.txt, rnd_7777_9_2299.txt, rnd_77_1_0.txt, rnd_77_1_14.txt, rnd_77_1_2.txt, rnd_77_9_0.txt, rnd_77_9_11.txt, rnd_77_9_54.txt, rnd_7_1_0.txt, rnd_7_1_2.txt, rnd_7_1_3.txt, rnd_7_9_0.txt, rnd_7_9_1.txt, rnd_7_9_2.txt, rndmx_100000_1_0.txt, sample1.txt, sample2.txt, sample3.txt |
Case Name |
Status |
Exec Time |
Memory |
mx_100000_1_0.txt |
AC |
17 ms |
45312 KB |
rnd_6_16666_4.txt |
AC |
16 ms |
45312 KB |
rnd_7777_1_0.txt |
AC |
15 ms |
45312 KB |
rnd_7777_1_2289.txt |
AC |
15 ms |
45312 KB |
rnd_7777_1_6444.txt |
AC |
15 ms |
45312 KB |
rnd_7777_9_0.txt |
AC |
16 ms |
45312 KB |
rnd_7777_9_1542.txt |
AC |
16 ms |
45312 KB |
rnd_7777_9_2299.txt |
AC |
16 ms |
45312 KB |
rnd_77_1_0.txt |
AC |
15 ms |
45312 KB |
rnd_77_1_14.txt |
AC |
15 ms |
45312 KB |
rnd_77_1_2.txt |
AC |
15 ms |
45312 KB |
rnd_77_9_0.txt |
AC |
15 ms |
45312 KB |
rnd_77_9_11.txt |
AC |
15 ms |
45312 KB |
rnd_77_9_54.txt |
AC |
15 ms |
45312 KB |
rnd_7_1_0.txt |
AC |
15 ms |
45312 KB |
rnd_7_1_2.txt |
AC |
15 ms |
45312 KB |
rnd_7_1_3.txt |
AC |
15 ms |
45312 KB |
rnd_7_9_0.txt |
AC |
15 ms |
45312 KB |
rnd_7_9_1.txt |
AC |
15 ms |
45312 KB |
rnd_7_9_2.txt |
AC |
15 ms |
45312 KB |
rndmx_100000_1_0.txt |
AC |
16 ms |
45312 KB |
sample1.txt |
AC |
15 ms |
45312 KB |
sample2.txt |
AC |
15 ms |
45312 KB |
sample3.txt |
AC |
15 ms |
45312 KB |