QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#140962#5440. P-P-Palindromemendicillin2WA 1ms3576kbC++142.1kb2023-08-17 01:59:202023-08-17 01:59:23

Judging History

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

  • [2023-08-17 01:59:23]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3576kb
  • [2023-08-17 01:59:20]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = int(a); i < int(b); i++)
#define trav(a, x) for (auto& a : x)
#define per(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()

template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;

using ll = int64_t;
using vi = vc<int>;
using pii = pair<int, int>;

// Author: maroonrk (modified)
// https://codeforces.com/contest/1738/submission/174140231
template<class S>
struct eertree{
	struct N{
		int suf,ser,l,r;
		int len(){return r-l;}
		map<int,int> ch;
		//array<int,26> ch;
	};
	vc<N> x;
	int dist(int v){
		if(x[v].suf<=0)return -1;
		return x[v].len()-x[x[v].suf].len();
	}
	int c;
	S s;
	eertree(){
		x.push_back({-1,-1,1,0,{}});
		x.push_back({0,-1,0,0,{}});
		c=1;
	}
	void reserve(int n) {
		s.reserve(n+5);
		x.reserve(n+5);
	}
	bool chk(int v,int i){
		int l=i-x[v].len();
		return l>0&&s[l-1]==s[i];
	}
	template<class t>
	int extend(t z){
		int i=sz(s);
		s.push_back(z);
		
		while(!chk(c,i))c=x[c].suf;
		if(x[c].ch.count(s[i])==0){
			int d=x[c].suf;
			if(d!=-1)while(!chk(d,i))d=x[d].suf;
			int e=d==-1?1:x[d].ch[s[i]];
			int f=x[c].ch[s[i]]=sz(x);
			x.push_back({e,e,i-x[c].len()-1,i+1,{}});
			if(dist(f)==dist(e))
				x[f].ser=x[e].ser;
		}
		return c=x[c].ch[s[i]];
	}
	N& operator[](int i){
		return x[i];
	}
};

int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	cout << fixed << setprecision(20);

	int N;
	cin >> N;
	eertree<vector<int>> et;
	const int MAX = 3e6;
	et.reserve(MAX);
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		const int L = int(s.size());
		for (int j = 0; j < L; j++) {
			int x = int(s[j] - 'a');
			et.extend(x);
		}
		et.extend(26 + 2*i);
		et.extend(26 + 2*i+1);
	}

	ll ans = 0;
	const int num = int(et.x.size());
	for (int v = 2; v < num; v++) {
		if (et[v].suf == et[v].ser) {
			ans++;
		} else {
			int period = et.dist(v);
			int len = et[v].len();
			ans += 2 * (len / period) - 1;
		}
	}
	ans -= 2*N;
	cout << ans << '\n';
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3576kb

input:

2
aaaa
aaa

output:

16

result:

ok 1 number(s): "16"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3544kb

input:

3
abaaa
abbbba
bbbaba

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3528kb

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

output:

15130

result:

ok 1 number(s): "15130"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3500kb

input:

3
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbb
bababababababaabababababa

output:

1332

result:

wrong answer 1st numbers differ - expected: '1282', found: '1332'