QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#505804 | #2428. Comma Sprinkler | Rico64 | AC ✓ | 207ms | 70292kb | C++23 | 2.6kb | 2024-08-05 11:40:09 | 2024-08-05 11:40:10 |
Judging History
answer
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;
int main() {
string input;
getline(cin, input);
unordered_map<string, int> sti;
vector<pair<int, pair<int, int>>> blocks;
for (int i = 0, l = -1; i < input.size(); ++i) {
char c = input[i];
if (c >= 'a' && c <= 'z') {
if (l == -1) l = i;
} else {
if (l >= 0) {
string ss = input.substr(l, i - l);
int id;
if (sti.count(ss)) {
id = sti[ss];
} else {
id = sti.size();
}
sti[ss] = id;
blocks.push_back({id, {l, i}});
l = -1;
}
}
}
// for (const auto& p : sti) cout << p.first << " : " << p.second << endl;
int n = sti.size();
unordered_set<int> graph[n * 2];
bool colored[n * 2];
fill(colored, colored + n * 2, false);
for (int i = 1; i < blocks.size(); ++i) {
if (blocks[i].second.first - blocks[i-1].second.second == 1) {
graph[blocks[i-1].first * 2 + 1].insert(blocks[i].first * 2);
graph[blocks[i].first * 2].insert(blocks[i-1].first * 2 + 1);
} else if (input[blocks[i-1].second.second] == ',') {
colored[blocks[i-1].first * 2 + 1] = true;
colored[blocks[i].first * 2] = true;
}
}
// for (int x = 0; x < n * 2; ++x) {
// cout << x << " : ";
// for (const int& y : graph[x]) {
// cout << y << ",";
// }
// cout << endl;
// }
queue<int> q;
for (int i = 0; i < n * 2; ++i) {
if (colored[i]) {
q.push(i);
}
}
fill(colored, colored + n * 2, false);
while (!q.empty()) {
int v = q.front(); q.pop();
if (colored[v]) continue;
colored[v] = true;
for (const int& ne : graph[v]) {
if (colored[ne]) continue;
q.push(ne);
}
}
for (int i = 0; i < blocks.size(); ++i) {
cout << input.substr(blocks[i].second.first, blocks[i].second.second - blocks[i].second.first);
if (i == blocks.size() - 1) {
cout << input.substr(blocks[i].second.second);
} else if (blocks[i + 1].second.first - blocks[i].second.second > 1 || !colored[blocks[i].first * 2 + 1]) {
cout << input.substr(blocks[i].second.second, blocks[i + 1].second.first - blocks[i].second.second);
} else {
cout << ", ";
}
}
cout << endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3824kb
Test #2:
score: 0
Accepted
time: 0ms
memory: 3572kb
Test #3:
score: 0
Accepted
time: 0ms
memory: 3816kb
Test #4:
score: 0
Accepted
time: 0ms
memory: 3596kb
Test #5:
score: 0
Accepted
time: 0ms
memory: 3568kb
Test #6:
score: 0
Accepted
time: 38ms
memory: 12912kb
Test #7:
score: 0
Accepted
time: 81ms
memory: 56528kb
Test #8:
score: 0
Accepted
time: 79ms
memory: 56544kb
Test #9:
score: 0
Accepted
time: 0ms
memory: 3744kb
Test #10:
score: 0
Accepted
time: 0ms
memory: 3828kb
Test #11:
score: 0
Accepted
time: 0ms
memory: 3652kb
Test #12:
score: 0
Accepted
time: 0ms
memory: 3604kb
Test #13:
score: 0
Accepted
time: 1ms
memory: 3928kb
Test #14:
score: 0
Accepted
time: 0ms
memory: 3680kb
Test #15:
score: 0
Accepted
time: 0ms
memory: 3816kb
Test #16:
score: 0
Accepted
time: 110ms
memory: 21172kb
Test #17:
score: 0
Accepted
time: 207ms
memory: 35680kb
Test #18:
score: 0
Accepted
time: 190ms
memory: 61488kb
Test #19:
score: 0
Accepted
time: 0ms
memory: 3592kb
Test #20:
score: 0
Accepted
time: 162ms
memory: 70292kb
Test #21:
score: 0
Accepted
time: 95ms
memory: 70020kb
Test #22:
score: 0
Accepted
time: 72ms
memory: 64716kb
Test #23:
score: 0
Accepted
time: 17ms
memory: 14532kb
Test #24:
score: 0
Accepted
time: 106ms
memory: 44772kb
Test #25:
score: 0
Accepted
time: 49ms
memory: 25164kb
Test #26:
score: 0
Accepted
time: 100ms
memory: 46144kb
Test #27:
score: 0
Accepted
time: 49ms
memory: 24284kb
Test #28:
score: 0
Accepted
time: 78ms
memory: 35660kb
Test #29:
score: 0
Accepted
time: 4ms
memory: 5256kb
Test #30:
score: 0
Accepted
time: 0ms
memory: 3608kb
Test #31:
score: 0
Accepted
time: 6ms
memory: 5476kb
Test #32:
score: 0
Accepted
time: 14ms
memory: 5344kb
Test #33:
score: 0
Accepted
time: 0ms
memory: 3516kb
Test #34:
score: 0
Accepted
time: 0ms
memory: 3632kb
Test #35:
score: 0
Accepted
time: 0ms
memory: 3480kb
Test #36:
score: 0
Accepted
time: 0ms
memory: 3808kb
Test #37:
score: 0
Accepted
time: 0ms
memory: 3744kb
Test #38:
score: 0
Accepted
time: 0ms
memory: 3820kb
Test #39:
score: 0
Accepted
time: 0ms
memory: 3472kb
Test #40:
score: 0
Accepted
time: 0ms
memory: 3772kb
Test #41:
score: 0
Accepted
time: 9ms
memory: 8008kb
Test #42:
score: 0
Accepted
time: 9ms
memory: 8060kb
Test #43:
score: 0
Accepted
time: 3ms
memory: 8104kb
Test #44:
score: 0
Accepted
time: 6ms
memory: 8392kb
Test #45:
score: 0
Accepted
time: 4ms
memory: 8372kb
Test #46:
score: 0
Accepted
time: 4ms
memory: 8384kb
Test #47:
score: 0
Accepted
time: 55ms
memory: 20436kb
Test #48:
score: 0
Accepted
time: 58ms
memory: 20416kb
Test #49:
score: 0
Accepted
time: 55ms
memory: 20476kb
Test #50:
score: 0
Accepted
time: 28ms
memory: 14796kb
Test #51:
score: 0
Accepted
time: 33ms
memory: 14772kb
Test #52:
score: 0
Accepted
time: 29ms
memory: 14940kb
Test #53:
score: 0
Accepted
time: 157ms
memory: 30972kb
Test #54:
score: 0
Accepted
time: 155ms
memory: 31140kb
Test #55:
score: 0
Accepted
time: 143ms
memory: 31380kb
Test #56:
score: 0
Accepted
time: 121ms
memory: 26380kb
Test #57:
score: 0
Accepted
time: 121ms
memory: 26192kb
Test #58:
score: 0
Accepted
time: 120ms
memory: 26496kb
Test #59:
score: 0
Accepted
time: 0ms
memory: 3772kb
Test #60:
score: 0
Accepted
time: 14ms
memory: 6112kb
Test #61:
score: 0
Accepted
time: 9ms
memory: 5180kb
Test #62:
score: 0
Accepted
time: 0ms
memory: 3608kb