【CSP-201903】消息传递接口

明明是一道暴力就能过的水题的,却因为优化思路错了导致一直RE。

只要模拟一下协程的工作原理就好,每次只处理一条线程的一条指令,然后换到下一条线程。

具体实现:开n条队列,读入时把相应的指令全部压到队列中。然后不断地扫这n条队列处理队列头部的指令。如果该指令的目标的队列头部的指令恰好能够和该条指令匹配,则将这两个指令出队。一直这样做下去直到经过一轮都没有任何指令得到处理时跳出。

由于每次至少处理两条指令,所以时间复杂度是$O(T \cdot n)$的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <vector>
#include <queue>
#include <sstream>
using namespace std;
struct command
{
enum command_type
{
send = 0,
receive = 1
};

command_type type;
int sender, target;

command(command_type _type, int _sender, int _target)
{
sender = _sender;
type = _type;
target = _target;
}
command(const string &str, int _sender)
{
sender = _sender;
if (str[0] == 'R')
type = command_type::receive;
else if (str[0] == 'S')
type = command_type::send;
target = stoi(str.substr(1));
}

bool operator==(const command &o)
{
return type == o.type && sender == o.sender && target == o.target;
}
};

int n;
vector<queue<command>> coms;

void init(int _n)
{
n = _n;
coms.clear();
coms.resize(n);
}
void push_command(int sender, const string &com)
{
coms[sender].emplace(com, sender);
}
bool work()
{
while (true)
{
bool all_empty = true;
for (int i = 0; i < n; i++)
all_empty &= coms[i].empty();
if (all_empty)
return true;

int solved = 0;
for (int i = 0; i < n; i++)
{
if (!coms[i].empty())
{
auto com = coms[i].front();
int j = coms[i].front().target;
if (!coms[j].empty())
{
auto next_com = coms[j].front();
if (next_com.target == i && (com.type ^ next_com.type))
{
coms[i].pop();
coms[j].pop();
solved++;
}
}
}
}

if (!solved)
return false;
}
}

int main()
{
int t, n;
cin >> t >> n;
cin.ignore();

while (t--)
{
init(n);
for (int i = 0; i < n; i++)
{
string s;
getline(cin, s);

stringstream ss;
ss << s;
while (!ss.eof())
{
ss >> s;
push_command(i, s);
}
}

cout << (work() ? 0 : 1) << endl;
}
return 0;
}
Author: ssttkkl
Link: https://ssttkkl.github.io/CSP/2019/12/%E3%80%90CSP-201903%E3%80%91%E6%B6%88%E6%81%AF%E4%BC%A0%E9%80%92%E6%8E%A5%E5%8F%A3/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.