QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#581168 | #4632. Card Shark | chuchu# | WA | 0ms | 3836kb | C++14 | 2.0kb | 2024-09-22 10:18:24 | 2024-09-22 10:18:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FINISH cerr << "FINISH" << endl;
#define debug(x) cerr << #x << " == " << x << endl
#define el '\n'
#define fir first
#define sec second
typedef long long ll;
typedef pair<int, int> PII;
const int mod = 1000000007;
const int inf = 0x3f3f3f3f;
const int N = 200020;
void solve()
{
int n, m, d, mx = -1;
cin >> n >> m >> d;
vector<vector<PII>> edge(m + 1);
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
int st = 0;
for (int i = 0; s[i]; i++) {
if (s[i] == '1') {
st = i;
break;
}
}
if (st + 1 == d) {
mx = max(mx, i);
}
int cnt = 0;
for (int i = st + 1; s[i]; i++) {
if (i % m == st && s[i] == '0') {
cout << "-1" << el;
return;
}
if (i % m != st && s[i] == '1') {
cout << "-1" << el;
return;
}
if (s[i] == '0') {
cnt++;
}
else {
cnt = 0;
}
}
if (st >= m || cnt >= m) {
cout << "-1" << el;
return;
}
edge[st].push_back(PII(m - 1 - cnt, i));
// cout << "addedge " << st << " " << m - 1 - cnt << " " << i << endl;
}
for (int i = 0; i <= m; i++) {
sort(edge[i].begin(), edge[i].end(),
[&](PII x, PII y) { return x.sec < y.sec; });
}
if (mx == -1) {
cout << "-1" << el;
return;
}
if (n == 1) {
cout << "1" << el;
return;
}
/*for (int i = 0; i < m; i++) {
for (auto [to, w] : edge[i]) {
cout << i << " " << to << " " << w << endl;
}
}*/
int st = d - 1;
vector<int> b(n + 1, 0);
vector<int> ans;
function<void(int)> dfs = [&](int x) {
for (int i = b[x]; i < edge[x].size();) {
b[x] = i + 1;
ans.push_back(edge[x][i].sec);
dfs(edge[x][i].fir);
break;
}
};
dfs(st);
if (ans.size() != n) {
cout << "-1" << el;
return;
}
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
cout << el;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3616kb
input:
5 4 3 0100010 00100 001000100 0010 0100010
output:
2 1 3 5 4
result:
ok single line: '2 1 3 5 4 '
Test #2:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
4 2 1 010 10101 010 10101
output:
2 1 4 3
result:
ok single line: '2 1 4 3 '
Test #3:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
1 5 3 001000010000100
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
2 5 3 01000 00010
output:
-1
result:
ok single line: '-1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
1 5 3 11111
output:
-1
result:
ok single line: '-1'
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 3544kb
input:
10 5 3 000010000100 0001000010000100001 000100 00010 00010000100 0010 00001000010000100001000010 00010 001 001000010
output:
-1
result:
wrong answer 1st lines differ - expected: '6 2 1 9 7 3 10 4 8 5', found: '-1'