QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#297966#4629. Longest Increasing Subsequencedefyers#WA 0ms3572kbC++172.6kb2024-01-05 15:01:352024-01-05 15:01:36

Judging History

你现在查看的是最新测评结果

  • [2024-01-05 15:01:36]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3572kb
  • [2024-01-05 15:01:35]
  • 提交

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'