QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#297966 | #4629. Longest Increasing Subsequence | defyers# | WA | 0ms | 3572kb | C++17 | 2.6kb | 2024-01-05 15:01:35 | 2024-01-05 15:01:36 |
Judging History
answer
#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")
#pragma GCC targetr("avx2")
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
#define sz(x) (int)(x.size())
vi eulerWalk(vector<vector<pii>> &gr, int nedges, int src = 0) {
int n = sz(gr);
vi D(n), its(n), eu(nedges), ret, s = {src};
D[src]++;
while (!s.empty()) {
int x = s.back(), y, e, &it = its[x], end = sz(gr[x]);
if (it == end) {
ret.push_back(x); s.pop_back(); continue;
}
tie(y, e) = gr[x][it++];
if (!eu[e]) {
D[x]--, D[y]++;
eu[e] = 1; s.push_back(y);
}
}
for (int x : D) if (x < 0 || sz(ret) != nedges+1) return {};
return {ret.rbegin(), ret.rend()};
}
void solve(int TC) {
int n, m, b;
cin >> n >> m >> b;
int sum = 0;
bool fail = false;
vector<pii> a(n);
for (int i = 0; i < n; i++) {
string s;
cin >> s;
int sz = s.size();
sum += sz;
int prev = -1;
int mn = -1;
int mx = -1;
for (int j = 0; j < sz; j++) {
if (s[j] == '1') {
if (prev == -1) {
prev = j;
mn = j;
mx = j;
}
else {
int diff = j - prev;
if (diff != m) fail = true;
mx = j;
prev = j;
}
}
else {
continue;
}
}
int pre = mn;
int last = sz - mx - 1;
if (prev != -1) a[i] = {pre, last};
else {
if (sz > (m - 1)) {
fail = true;
break;
}
else {
a[i] = {sz, sz};
}
}
}
int ed = (sum - 1) % m - (b - 1);
ed = (ed % m + m) % m;
cout << ed << endl;
if (fail) {
cout << -1 << "\n";
return;
}
// for (int i = 0; i < n; i++) {
// cout << a[i].first << " " << a[i].second << endl;
// }
int E = 0;
vector<vector<pii>> g(n + 1 + m);
for (int i = 0; i < n; i++) {
g[(n + 1) + a[i].first].push_back({i + 1, E++});
g[i + 1].push_back({(n + 1) + (m - 1 - a[i].second), E++});
}
// g[(n + 1) + ed].push_back({(n + 1) + (b - 1), E++});
for (int i = 0; i < n + 1 + m; i++) {
for (auto [v, w]: g[i]) {
cout << i << " -> " << v << " ecnt: " << w << endl;
}
}
auto res = eulerWalk(g, E, (n + 1) + b - 1);
for (auto x: res) {
cout << x << " ";
}
cout << "\n";
if (res.size() == 0) {
cout << "-1\n";
return;
}
vector<int> ans;
for (auto x: res) {
if (x >= 1 && x <= n) {
ans.push_back(x);
}
}
for (int i = 0; i < n; i++) {
cout << ans[i] << " \n"[i == n - 1];
}
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cout << fixed << setprecision(10);
int t = 1;
// cin >> t;
for (int i = 1; i <= t; i++) {
solve(i);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3572kb
input:
7 7 41 53 58 75 78 81
output:
4 1 -> 12 ecnt: 1 2 -> 12 ecnt: 3 3 -> 12 ecnt: 5 4 -> 12 ecnt: 7 5 -> 14 ecnt: 9 6 -> 14 ecnt: 11 7 -> 14 ecnt: 13 8 -> 6 ecnt: 10 8 -> 7 ecnt: 12 9 -> 5 ecnt: 8 10 -> 1 ecnt: 0 10 -> 2 ecnt: 2 10 -> 3 ecnt: 4 10 -> 4 ecnt: 6 -1
result:
wrong answer 1st lines differ - expected: '22', found: '4'