QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#165117#2428. Comma SprinklerPetroTarnavskyi#AC ✓75ms77464kbC++171.7kb2023-09-05 16:06:342023-09-05 16:06:34

Judging History

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

  • [2023-09-05 16:06:34]
  • 评测
  • 测评结果:AC
  • 用时:75ms
  • 内存:77464kb
  • [2023-09-05 16:06:34]
  • 提交

answer

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

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a); i >= (b); i--)
#define FILL(a, b) memset(a, b, sizeof(a))
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int N = 1'000'447;
unordered_map<string, int> m;
VI g[2][N];
bool used[2][N];

void dfs(int i, int v)
{
	used[i][v] = 1;
	for (auto& to : g[i][v])
		if (!used[i ^ 1][to])
			dfs(i ^ 1, to);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s;
	getline(cin, s);
	m.reserve(N);
	bool prev = 0;
	int idx = 0;
	vector<PII> v;
	set<char> se;
	se.insert(' ');
	se.insert(',');
	se.insert('.');
	int k = -1;
	FOR (i, 0, SZ(s))
	{
		string word = "";
		while (!se.count(s[i]))
			word += s[i++];
		int j = 0;
		if (m.count(word))
			j = m[word];
		else
			m[word] = j = idx++;
		if (prev)
		{
			v.PB({1, j});
		}
		if (k != -1)
		{
			g[0][k].PB(j);
			g[1][j].PB(k);
		}
		if (s[i] == ',')
		{
			v.PB({0, j});
			prev = 1;
		}
		else
			prev = 0;
		if (s[i] == '.')
			k = -1;
		else
			k = j;
		if (s[i] == ',' || s[i] == '.') i++;
	}
	for (auto [i, u] : v)
		if (!used[i][u])
			dfs(i, u);
	FOR (i, 0, SZ(s))
	{
		string word = "";
		while (!se.count(s[i]))
			word += s[i++];
		int	j = m[word];
		cout << word;
		if (s[i] == ' ' && used[0][j])
		{
			cout << ",";
		}
		cout << s[i];
		if (s[i] == ',' || s[i] == '.') 
		{
			cout << ' ';
			i++;
		}
	}
	cout << '\n';
}



Details

Test #1:

score: 100
Accepted
time: 5ms
memory: 58744kb

Test #2:

score: 0
Accepted
time: 7ms
memory: 58780kb

Test #3:

score: 0
Accepted
time: 4ms
memory: 59108kb

Test #4:

score: 0
Accepted
time: 3ms
memory: 59796kb

Test #5:

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

Test #6:

score: 0
Accepted
time: 47ms
memory: 65664kb

Test #7:

score: 0
Accepted
time: 54ms
memory: 75016kb

Test #8:

score: 0
Accepted
time: 47ms
memory: 75432kb

Test #9:

score: 0
Accepted
time: 4ms
memory: 59400kb

Test #10:

score: 0
Accepted
time: 5ms
memory: 59892kb

Test #11:

score: 0
Accepted
time: 7ms
memory: 58616kb

Test #12:

score: 0
Accepted
time: 3ms
memory: 58736kb

Test #13:

score: 0
Accepted
time: 3ms
memory: 59916kb

Test #14:

score: 0
Accepted
time: 10ms
memory: 58628kb

Test #15:

score: 0
Accepted
time: 16ms
memory: 58400kb

Test #16:

score: 0
Accepted
time: 52ms
memory: 65796kb

Test #17:

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

Test #18:

score: 0
Accepted
time: 75ms
memory: 71976kb

Test #19:

score: 0
Accepted
time: 7ms
memory: 59000kb

Test #20:

score: 0
Accepted
time: 71ms
memory: 75240kb

Test #21:

score: 0
Accepted
time: 65ms
memory: 77464kb

Test #22:

score: 0
Accepted
time: 42ms
memory: 74884kb

Test #23:

score: 0
Accepted
time: 8ms
memory: 64204kb

Test #24:

score: 0
Accepted
time: 56ms
memory: 76456kb

Test #25:

score: 0
Accepted
time: 63ms
memory: 77160kb

Test #26:

score: 0
Accepted
time: 63ms
memory: 71244kb

Test #27:

score: 0
Accepted
time: 35ms
memory: 65824kb

Test #28:

score: 0
Accepted
time: 58ms
memory: 73872kb

Test #29:

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

Test #30:

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

Test #31:

score: 0
Accepted
time: 10ms
memory: 61840kb

Test #32:

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

Test #33:

score: 0
Accepted
time: 8ms
memory: 59652kb

Test #34:

score: 0
Accepted
time: 4ms
memory: 60328kb

Test #35:

score: 0
Accepted
time: 7ms
memory: 58872kb

Test #36:

score: 0
Accepted
time: 4ms
memory: 58464kb

Test #37:

score: 0
Accepted
time: 7ms
memory: 59968kb

Test #38:

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

Test #39:

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

Test #40:

score: 0
Accepted
time: 16ms
memory: 60312kb

Test #41:

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

Test #42:

score: 0
Accepted
time: 5ms
memory: 60492kb

Test #43:

score: 0
Accepted
time: 8ms
memory: 59948kb

Test #44:

score: 0
Accepted
time: 7ms
memory: 61380kb

Test #45:

score: 0
Accepted
time: 7ms
memory: 60052kb

Test #46:

score: 0
Accepted
time: 9ms
memory: 60244kb

Test #47:

score: 0
Accepted
time: 36ms
memory: 63932kb

Test #48:

score: 0
Accepted
time: 29ms
memory: 63540kb

Test #49:

score: 0
Accepted
time: 27ms
memory: 62884kb

Test #50:

score: 0
Accepted
time: 25ms
memory: 63064kb

Test #51:

score: 0
Accepted
time: 19ms
memory: 61140kb

Test #52:

score: 0
Accepted
time: 18ms
memory: 61832kb

Test #53:

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

Test #54:

score: 0
Accepted
time: 52ms
memory: 64528kb

Test #55:

score: 0
Accepted
time: 61ms
memory: 66228kb

Test #56:

score: 0
Accepted
time: 39ms
memory: 64520kb

Test #57:

score: 0
Accepted
time: 43ms
memory: 64124kb

Test #58:

score: 0
Accepted
time: 41ms
memory: 65464kb

Test #59:

score: 0
Accepted
time: 5ms
memory: 58416kb

Test #60:

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

Test #61:

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

Test #62:

score: 0
Accepted
time: 3ms
memory: 59196kb