QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#607897#2428. Comma SprinklerLJY_ljyTL 69ms131988kbC++112.2kb2024-10-03 16:57:372024-10-03 16:57:38

Judging History

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

  • [2024-10-03 16:57:38]
  • 评测
  • 测评结果:TL
  • 用时:69ms
  • 内存:131988kb
  • [2024-10-03 16:57:37]
  • 提交

answer

//Trie树(字典树)练习 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
using namespace std;

const int MAXN = 1000010;
char str[MAXN], Ans[MAXN];
int exist[MAXN], End[MAXN], len, Bound[MAXN];
int eid, cnt, nex[MAXN][30], Type[MAXN];
set<int> G[MAXN][2]; 
bool used[MAXN][2];
queue<int> q1, q2;
// 空格 0, 句号 1,逗号 2

int main() {
	while (scanf("%s", str + 1) != EOF) {
		int n = strlen(str + 1), m;
		cnt++;
		if ('a' <= str[n] && str[n] <= 'z') m = n;
		else m = n - 1;
		Type[cnt] = (Type[cnt - 1] % 3) * 3;
		if ('.' == str[n]) Type[cnt] ++;
		if (',' == str[n]) Type[cnt] += 2; 
		for (int i = len + 1; i <= len + m; i++)
			Ans[i] = str[i - len];
		len = len + m;
		Bound[cnt] = len;
		int p = 0;
		for (int i = 1; i <= m; i++) {
			int c = str[i] - 'a';
			if (!nex[p][c]) nex[p][c] = ++eid;
			p = nex[p][c];
 		}
 		if (Type[cnt] % 3 == 2 && exist[p] % 3 == 0)
 			exist[p] += 2;
 		if (Type[cnt] / 3 == 2 && exist[p] / 3 == 0)
 			exist[p] += 6; 
 		End[cnt] = p;
	}
	for (int i = 1; i <= cnt; i++) {
		if (Type[i + 1] / 3 != 1)
			G[End[i]][0].insert(End[i + 1]); // ..., -> ,... 
		if (Type[i - 1] % 3 != 1) 
			G[End[i]][1].insert(End[i - 1]); // ,... -> ...,
	}
	for (int i = 1; i <= cnt; i++) {
		if (exist[End[i]] % 3 == 2) {
			q1.push(End[i]);
			used[End[i]][0] = true;
		}
		if (exist[End[i]] / 3 == 2) {
			q2.push(End[i]);
			used[End[i]][1] = true;
		} 
	}
	while ((!q1.empty()) || (!q2.empty())) {
		while (!q1.empty()) {
			int x = q1.front();
			for (auto y:G[x][0]) {
				if (!used[y][1]) {
					used[y][1] = true;
					q2.push(y);
				}
			}
			q1.pop();
		}
		while (!q2.empty()) {
			int x = q2.front();
			for (auto y:G[x][1]) {
				if (!used[y][0]) {
					used[y][0] = true;
					q1.push(y);
				}
			}
			q2.pop();
		}
	} 
	for (int i = 1; i <= cnt; i++) {
		for (int j = Bound[i - 1] + 1; j <= Bound[i]; j++)
			printf("%c", Ans[j]); 
		if (Type[i] % 3 != 1 && (used[End[i]][0] || used[End[i + 1]][1])) printf(",");
		if (Type[i] % 3 == 1) printf(".");
		printf(" ");
	}
	return 0;
}  

Details

Test #1:

score: 100
Accepted
time: 11ms
memory: 102168kb

Test #2:

score: 0
Accepted
time: 12ms
memory: 99976kb

Test #3:

score: 0
Accepted
time: 12ms
memory: 102292kb

Test #4:

score: 0
Accepted
time: 17ms
memory: 102112kb

Test #5:

score: 0
Accepted
time: 11ms
memory: 100328kb

Test #6:

score: 0
Accepted
time: 68ms
memory: 114452kb

Test #7:

score: 0
Accepted
time: 59ms
memory: 130836kb

Test #8:

score: 0
Accepted
time: 69ms
memory: 131988kb

Test #9:

score: 0
Accepted
time: 11ms
memory: 102068kb

Test #10:

score: 0
Accepted
time: 15ms
memory: 102132kb

Test #11:

score: 0
Accepted
time: 11ms
memory: 102072kb

Test #12:

score: 0
Accepted
time: 12ms
memory: 102068kb

Test #13:

score: 0
Accepted
time: 11ms
memory: 100132kb

Test #14:

score: 0
Accepted
time: 11ms
memory: 102156kb

Test #15:

score: 0
Accepted
time: 15ms
memory: 102140kb

Test #16:

score: -100
Time Limit Exceeded