QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#313455 | #8176. Next TTPC 3 | ucup-team266# | WA | 2ms | 5272kb | C++23 | 2.1kb | 2024-01-24 19:29:13 | 2024-01-24 19:29:14 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
vector<int> gen(string s,string t,string pat)
{
vector<int> res(sz(s)*sz(t));
for(int i=0;i<sz(res);i++)
if(s[i%sz(s)]==pat[0]&&t[i%sz(t)]==pat[1])
res[i]=1;
return res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
n--;
string A,B,C,D;
cin>>A>>B>>C>>D;
vector<int> v1=gen(A,B,"TT"),v2=gen(C,D,"PC");
int a=sz(v1),b=sz(v2),g=__gcd(a,b);
vector<vector<int>> vs(g),vt(g);
for(int i=0;i<a;i++)
vs[i%g].pb(v1[i]);
for(int i=0;i<b;i++)
vt[i%g].pb(v2[i]);
ll tot=0;
for(int i=0;i<g;i++)
tot+=accumulate(ALL(vs[i]),0ll)*accumulate(ALL(vt[i]),0ll);
if(!tot) die("-1");
ll ans=1ll*a*b/g*(n/tot);
n%=tot;
ll l=0,r=a*b/g;
while(l<r)
{
ll mid=(l+r)/2;
ll cnt=0;
for(int i=0;i<g;i++)
{
vector<ll> psum(b/g);
vector<int> ord(b/g);
for(int j=0;j<sz(vt[i]);j++)
psum[j]=vt[i][j];
int c=0;
ll lst=0;
for(int j=0;j<sz(vt[i]);j++)
{
int x=1ll*sz(vs[i])*j%sz(vt[i]);
ord[x]=c++;
psum[x]+=lst;
lst=psum[x];
}
for(int j=0;j<sz(vs[i]);j++)
if(vs[i][j])
{
int pos=j*g+i;
if(mid<pos) continue;
ll times2=(mid-pos)/a+1;
int st=j%sz(vt[i]);
int nd=(j+(times2-1)*sz(vs[i]))%sz(vt[i]);
if(ord[nd]>=ord[st])
cnt+=psum[nd]-psum[st]+vt[i][st];
else
cnt+=lst-psum[st]+psum[nd]+vt[i][st];
}
}
if(cnt<=n)
l=mid+1;
else
r=mid;
}
cout<<ans+l+1<<endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3804kb
input:
3 TTPC TLE P AC
output:
34
result:
ok "34"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
670055 TF OITFKONTO GFPPNPWTZP CCZFB
output:
-1
result:
ok "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
910359 TOKYO TECH PROGRAMMING CONTEST
output:
1401951321
result:
ok "1401951321"
Test #4:
score: -100
Wrong Answer
time: 2ms
memory: 5272kb
input:
518530 TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT...
output:
1
result:
wrong answer 1st words differ - expected: '518530', found: '1'