QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#313455#8176. Next TTPC 3ucup-team266#WA 2ms5272kbC++232.1kb2024-01-24 19:29:132024-01-24 19:29:14

Judging History

你现在查看的是最新测评结果

  • [2024-01-24 19:29:14]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:5272kb
  • [2024-01-24 19:29:13]
  • 提交

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'