QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#359635#6567. Repetitive String Inventionnkamzabek#WA 254ms11208kbC++232.0kb2024-03-20 19:38:272024-03-20 19:38:28

Judging History

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

  • [2024-03-20 19:38:28]
  • 评测
  • 测评结果:WA
  • 用时:254ms
  • 内存:11208kb
  • [2024-03-20 19:38:27]
  • 提交

answer

#include <bits/stdc++.h>

#define f first
#define s second
#define sz(s) (int)s.size()
#define pb push_back
#define int long long

using namespace std;

using vi = vector<int>;

const int N = (int)5e3 + 100;

string s, t;
int n, m;

const int p[] = {(int)1e6 + 33, (int)1e6 + 7};
const int mod[] = {(int)1e9 + 7, (int)1e9 + 9};
int h[N][2];
int pw[N][2];

pair<int, int> get(int l, int r){
	int a = (h[r][0] - pw[r - l + 1][0] * 1ll * h[l - 1][0] % mod[0]);
	int b = (h[r][1] - pw[r - l + 1][1] * 1ll * h[l - 1][1] % mod[1]);
	
	if(a < 0)
		a += mod[0];
	if(b < 0)
		b += mod[1];
	return {a, b};
}


struct HASH{
  size_t operator()(const pair<int,int>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};

main(){
	ios_base :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> s;
	n = s.size();
	pw[0][0] = pw[0][1] = 1;

	for(int i = 0; i < n; i++){
		for(int it = 0; it < 2; it++){
			h[i + 1][it] = (h[i][it] * 1ll * p[it] + s[i]) % mod[it];
			pw[i + 1][it] = (pw[i][it] * 1ll * p[it]) % mod[it];
		}
	}
	
	unordered_map<pair<int, int>, int, HASH> cnt, cnt1;
	long long ans = 0;
	for(int i = 1; i <= n; i++){
		int s[2] = {};
		for(int j = i; j <= n; j++){
			ans += cnt[get(i, j)];
			ans += cnt1[get(i, j)];
		}
		for(int j = 1; j <= i; j++){			
			for(int k = j; k < i; k++){
				int len = k - j + 1;
				if(get(j, j + len - 1) == get(i - len + 1, i)){
					if(j + len <= i - len)
						cnt1[get(j + len, i - len)]++;	
				}
			}
			cnt[get(j, i)]++;
		
		}
	}
	
	reverse(s.begin(), s.end());
	cnt1.clear();
	
	for(int i = 1; i <= n; i++){
		for(int j = i; j <= n; j++){
			ans += cnt1[get(i, j)];
		}
		for(int j = 1; j <= i; j++){			
			for(int k = j; k < i; k++){
				int len = k - j + 1;
				if(get(j, j + len - 1) == get(i - len + 1, i)){
					if(j + len <= i - len)
						cnt1[get(j + len, i - len)]++;	
				}
			}
		}
	}
	
	cout << ans << "\n";
}

详细

Test #1:

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

input:

aaaa

output:

9

result:

ok single line: '9'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

axabxbcxcdxd

output:

22

result:

ok single line: '22'

Test #3:

score: 0
Accepted
time: 254ms
memory: 3648kb

input:

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

536006700

result:

ok single line: '536006700'

Test #4:

score: 0
Accepted
time: 219ms
memory: 3756kb

input:

abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...

output:

136016600

result:

ok single line: '136016600'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

a

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

ab

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

aa

output:

1

result:

ok single line: '1'

Test #8:

score: -100
Wrong Answer
time: 163ms
memory: 11208kb

input:

bbbbbrrrrbrbrrbrbrbrbbrrbbbbrrbrrbrbrbrrrrrbbbrrbrrbbrrrbbbbbrrrrbbrbbrrrrrbbrrrbbbbbrbbrbbbrbrrbrrrrrrrrbbrbrbbrrrrrrbbbbbrbrrrrbrrbbrbrrrrrbrbrbbrbrrbrrrrbrbbrbrrbrrbbbbrrrrrbrbbrbbrrrrrbrbrbrbbbrrrrrrrbbbbbbrrbrbrrrrrbbbrbrrrrbbbbrrbrrbbbbbbbrbbbbrrrbrbbbrrrrrrbbbbbrbrrbbbbrbrbrrbbrrrbbbrbbbrbbrr...

output:

204856

result:

wrong answer 1st lines differ - expected: '209015', found: '204856'