惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

D
Docker
小众软件
小众软件
让小产品的独立变现更简单 - ezindie.com
让小产品的独立变现更简单 - ezindie.com
freeCodeCamp Programming Tutorials: Python, JavaScript, Git & More
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
酷 壳 – CoolShell
酷 壳 – CoolShell
Apple Machine Learning Research
Apple Machine Learning Research
月光博客
月光博客
人人都是产品经理
人人都是产品经理
大猫的无限游戏
大猫的无限游戏
V
V2EX
阮一峰的网络日志
阮一峰的网络日志
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
博客园 - Franky
WordPress大学
WordPress大学
有赞技术团队
有赞技术团队
Hugging Face - Blog
Hugging Face - Blog
Jina AI
Jina AI
博客园 - 聂微东
S
SegmentFault 最新的问题
量子位
宝玉的分享
宝玉的分享
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
博客园_首页

Tifa's Blog

随笔 - 关于 C++ 模板的部分特化 随笔 - Miller-Rabin + Pollard-Rho 分解质因子的时间复杂度分析 随笔 - 批量重命名 APK 文件的 Python 脚本 VP 记录 - 2021 CCPC 哈尔滨站 VP 记录 - 2023 ICPC 亚洲区域赛 (南京) VP 记录 - 2023 CCPC 哈尔滨站 VP 记录 - 2023 CCPC 桂林站 VP 记录 - 2023 ICPC 亚洲区域赛 (网络预选赛 Ⅰ) VP 记录 - 2021 ICPC 亚洲区域赛 (澳门) 题解 - [Luogu P7486] 「Stoi2031」彩虹 拟阵简介(unfin) 题解 - [Luogu P5824] 十二重计数法 随笔 - C++ 的高维向量 | Tifa's Blog 目录 - 算法竞赛模板 | Tifa's Blog 目录 - 学术垃圾 | Tifa's Blog 比赛记录 - Codeforces Round #842 (Div. 2) 比赛记录 - Hello 2023 | Tifa's Blog 比赛记录 - Codeforces Round #841 (Div. 2) and Divide by Zero 2022 随笔 - C++ 基于标签分发的线性筛 | Tifa's Blog VP 记录 - 2022 ICPC 亚洲区域赛 (杭州)
VP 记录 - 2022 ICPC 亚洲区域赛 (济南)
Tifa · 2022-12-09 · via Tifa's Blog
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include <bits/stdc++.h>
using ll = long long;
template <class T>
using vc = std::vector<T>;
#define for_(i, l, r, v...) for (ll i = (l), i##e = (r), ##v; i <= i##e; ++i)
template <typename... Ts>
void dec(Ts &...x) {
((--x), ...);
}
template <typename... Ts>
void inc(Ts &...x) {
((++x), ...);
}
using namespace std;
stringstream ss;
struct Node {
int m;
vc<tuple<int, int, int>> t;
vc<tuple<int, int>> frozen;
vc<string> state;
vc<bool> vis, chosen;
Node(int m): m(m), t(), state(m), vis(m), chosen(m) {}
void parse() {
for_(i, 0, m - 1) {
ss.clear();
ss << state[i];
char op;
ss >> op;
if (op == '.') continue;
if (op == '-') {
int x;
ss >> x;
t.emplace_back(i, x, -1);
continue;
}
if (op == '+') {
int x, y;
ss >> x;
ss.get();
ss >> y;
t.emplace_back(i, x, y);
continue;
}
int x, y;
ss >> x >> y;
t.emplace_back(i, y - x, -1);
frozen.emplace_back(t.size() - 1, x);
}
}
pair<int, ll> score() {
int cnt = 0;
ll tm = 0;
for (auto [_, x, i] : t)
if (i >= 0) {
tm += i + 20 * (x - 1);
++cnt;
}
return {cnt, tm};
}
bool valid(pair<int, ll> const &s) {
if (frozen.empty()) return score() == s;
pair target = score();
if (target > s) return 0;
int fac = s.first - target.first;
ll ftm = s.second - target.second;
for_(i, 0, (1 << frozen.size()) - 1) {
if (__builtin_popcountll(i) != fac) continue;
ll minftm = 240 * fac, rftm = 59 * fac, minsp = 0, rsp = 0;
for (int j = 0; j < frozen.size(); ++j) {
if (!(i & (1 << j))) continue;
auto &&[id_t, x] = frozen[j];
auto &&[id, cnt, tm] = t[id_t];
minsp += 20 * cnt;
rsp += 20 * (x - 1);
}
if (ftm < minftm + minsp || ftm > minftm + rftm + minsp + rsp) continue;
for (int j = 0; j < frozen.size(); ++j) {
if (i & (1 << j)) continue;
auto &&[id_t, x] = frozen[j];
auto &[id, cnt, tm] = t[id_t];
cnt += x;
}
for (int j = 0; j < frozen.size(); ++j) {
if (!(i & (1 << j))) continue;
auto &[id_t, x] = frozen[j];
auto &[id, cnt, tm] = t[id_t];
tm = 240;
++cnt;
--x;
}
ftm -= minftm + minsp;
if (ftm > rftm)
for (int j = 0; j < frozen.size(); ++j) {
if (!(i & (1 << j))) continue;
auto &&[id_t, x] = frozen[j];
auto &[id, cnt, tm] = t[id_t];
int _ = min<int>((ftm - rftm) / 20 + (rftm > 20), x);
cnt += _;
if ((ftm -= 20 * _) <= rftm) break;
}
if (ftm)
for (int j = 0; j < frozen.size(); ++j) {
if (!(i & (1 << j))) continue;
auto &&[id_t, x] = frozen[j];
auto &[id, cnt, tm] = t[id_t];
tm += min(59ll, ftm);
if (!(ftm -= min(59ll, ftm))) break;
}
return 1;
}
return 0;
}
void pnt() {
for (auto &i : state) i = ".";
for (auto [id, cnt, tm] : t) {
string _;
ss.clear();
ss << cnt;
ss >> _;
if (tm == -1) state[id] = "- " + _;
else {
state[id] = "+ " + _ + '/';
ss.clear();
ss << tm;
ss >> _;
state[id] += _;
}
}
}
};
istream &operator>>(istream &is, Node &p) {
for (auto &i : p.state)
while (i.empty()) getline(cin, i);
return is;
}
ostream &operator<<(ostream &os, Node &p) {
p.pnt();
for (auto const &i : p.state) os << i << '\n';
return os;
}
void solve(int t_ = 0) {
int n, m;
cin >> n >> m;
for_(i, 1, n) {
pair<int, ll> score;
cin >> score.first >> score.second;
Node p(m);
cin >> p;
p.parse();
auto [x, y] = p.score();
if (!p.valid(score)) {
cout << "No\n";
continue;
}
cout << "Yes\n";
cout << p;
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cerr << std::fixed << std::setprecision(6);
int i_ = 0;
solve(i_);
return 0;
}