QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#123348#5666. Repetitive ElementsGenshinImpactsFault#AC ✓6ms3520kbC++141.7kb2023-07-12 13:05:512023-07-12 13:05:55

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-12 13:05:55]
  • 评测
  • 测评结果:AC
  • 用时:6ms
  • 内存:3520kb
  • [2023-07-12 13:05:51]
  • 提交

answer

#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define fr first
#define sd second
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
inline ll read()
{
	char ch = getchar();
	ll s = 0,w = 1;
	while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9'){s = s * 10 + ch -'0'; ch = getchar();}
	return s * w;
}
int number(char c)
{
	if(c == 'A') return 1;
	if(c == 'T') return 2;
	if(c == 'C') return 3;
	if(c == 'G') return 4;
	exit(-1);
}
const int mod = 998244353, seed = 131;
int n;
int ksm(int a, int b)
{
	int ans = 1;
	while(b){if(b & 1)ans=1LL*ans*a%mod;b >>= 1; a=1LL*a*a%mod;}
	return ans;
}
#define N 110
int H[N], h[N], invH[N];
int a[N]; char s[N];
int ck(int l1,int r1,int l2,int r2)
{
	int w1 = (h[r1] + mod - h[l1 - 1])%mod;
	int w2 = (h[r2] + mod - h[l2 - 1])%mod;
	return (1LL*w2*invH[l2-l1]%mod==w1);
}
int sol(int l,int r)
{
	int ans = 1, len = r - l + 1;
	int t = r + 1;
	FOR(i,r+1,n-len+1)if(i >= t)
	{
		if(ck(l,r,i,i+len-1)){ans ++;t = i + len;}
	}
	return ans;
}
void sol()
{
	scanf("%s",s+1);
	n = strlen(s+1);
	FOR(i,1,n)a[i]=number(s[i]);
	H[0] = 1; FOR(i,1,n)H[i] = 1LL * H[i-1] * seed % mod;
	invH[n]=ksm(H[n],mod-2);REP(i,n-1,0)invH[i]=1LL * invH[i+1] * seed % mod;
	FOR(i,1,n)h[i] = (h[i-1] + 1LL * a[i] * H[i] % mod)%mod;
	int L = inf, R = inf, mx = 0;
	FOR(l,1,n)FOR(r,l,n)
	{
		int num = sol(l,r);
		if(num >= 2 && r - l + 1 > R - L + 1)L = l, R = r, mx = num;
	}
	FOR(i,L,R)cout<<s[i];cout << '\n';
}
signed main()
{
	int T = read();
	while(T --) sol();	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3336kb

input:

5
TATCGATCGAGTTGT
TCCGCGAGCGAGTCTCTCCATT
GTTTCATCATACGAGGCCCCATACGCGCTGG
AGATGGGATCCTTATG
GCCCTTAGGCATGGGATGTCGTTTCTTG

output:

ATCG
GCGA
CATACG
GAT
CTT

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 6ms
memory: 3520kb

input:

50
TTGACAACTTCAGGTTGGCACTCCTTCATTTGGATTTCGGAATAATAGTTTTCTGCTCTGCC
ATCCTATTCGGGGATAGGAGAGATGGGTTGCCGCTATAAAAGCATTTGAACTCCATTTCACTCCGTTGGCTAGGGGTCGCACTG
CCGTAATATAAAGACTCGGAATTCCAATAGCTGCTATTTGCGAGTATGTGACTGAAAACACACCTATAAATATTAGCTGCGTACAAGCTA
ATGGCTGCATGCAGGGTCGACTAGACACACTTTGTCT
TTGAGGATGTCGACGTGTCT...

output:

CTTCA
CATTT
TAGCTGC
TGCA
ACGTG
GCGCCGG
CTCTT
AGTAT
AGAG
ACAG
TAT
TGAC
CTTG
CGTC
TACTGG
GCCGGT
GAA
CAGTA
GCGT
GGTT
CCCT
GAG
TAGAC
GGTGC
GCAGT
TGAG
ATCAA
CCACACA
GAGTC
ATGTA
ATGGTA
TATA
TATGAA
TTCC
CATACG
TACCA
TTAG
GGAATGT
CAGG
GCT
AAG
CTGT
GGAT
TCTTC
AAAAC
ATG
GATAA
TTA
ACATAT
CAAT

result:

ok 50 lines