답안 #1067227

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1067227	2024-08-20T13:10:17 Z	sleepntsheep	Alternating Current (BOI18_alternating)	C++17	0 / 100	57 ms	18448 KB

alternating

#include <stdio.h>
#include <queue>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>

using namespace std;

template <typename T>
using ve = vector<T>;

template <typename T, int sz>
using ar = array<T, sz>;

int n, m;
char ans[1<<18];

int main() {
	scanf("%d%d", &n, &m);
	ve<int> col(m);
	ve<set<int> > g(m);
	ve<ar<int, 2>> a(m);
	ve<ve<int>> at(n+1);

	int j = 0;
	for (auto &[x, y] : a) {
		scanf("%d%d", &x, &y), --x, --y;
		if (x <= y)
			at[x].push_back(j), at[y + 1].push_back(j);
		else at[0].push_back(j), at[y + 1].push_back(j),
			at[x].push_back(j), at[n].push_back(j);
		++j;
	}


	set<int> walk;
	for (int i = 0; i < n; ++i) {
		for (auto j : at[i]) 
			if (0 == walk.count(j)) walk.insert(j);
			else walk.erase(j);
		if (walk.size() == 2) {
			g[*walk.begin()].insert(*++walk.begin());
			g[*++walk.begin()].insert(*walk.begin());
		}
		if (walk.size() < 2) exit(0 * puts("impossible"));
	}


	auto bicolor = [&](int u) {
		queue<int> q;
		q.emplace(u); col[u] = 1;
		while (q.size()) {
			int x = q.front();
			q.pop();
			for (auto v : g[x]) {
				if (col[v] == col[x])
					exit(0 * puts("impossible"));
				if (not col[v]) {
					col[v] = col[x] == 1 ? 2 : 1;
					q.push(x);
				}
			}
		}
	};

	for (int i = 0; i < m; ++i) if (g[i].size() and col[i] == 0) bicolor(i);


	walk.clear();
	ar<int, 3> cnt {};
	for (int i = 0; i < n; ++i) {
		for (auto j : at[i]) 
			if (0 == walk.count(j)) walk.insert(j), ++cnt[col[j]];
			else walk.erase(j), --cnt[col[j]];
		if (walk.size() >= 3) {
			int x[3] = {*walk.begin(), *++walk.begin(), *++++walk.begin()};
			if (cnt[1] and cnt[2]) continue;
			if (not cnt[1] and not cnt[2]) {
				col[x[0]] = 1;
				col[x[1]] = 2;
				++cnt[1], ++cnt[2];
			} else if (not cnt[1]) {
				for (int j : {0, 1, 2}) if (col[x[j]] == 0)  {
					col[x[j]] = 1;
					++cnt[1];
					break;
				}
			} else {
				for (int j : {0, 1, 2}) if (col[x[j]] == 0)  {
					col[x[j]] = 2;
					++cnt[2];
					break;
				}

			}
		}

		if (not cnt[1] or not cnt[2])
			exit(0 * puts("impossible"));
	}

	for (int i = 0; i < m; ++i) putchar(col[i] == 1 ? '1' : '0');
	return 0;
}

Compilation message

alternating.cpp: In function 'int main()':
alternating.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
alternating.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   scanf("%d%d", &x, &y), --x, --y;
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	424 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	600 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	344 KB	Output is correct
18	Incorrect	0 ms	348 KB	'impossible' claimed, but there is a solution
19	Halted	0 ms	0 KB	-

Subtask #2
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	424 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	600 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	344 KB	Output is correct
18	Incorrect	0 ms	348 KB	'impossible' claimed, but there is a solution
19	Halted	0 ms	0 KB	-

Subtask #3
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	424 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	600 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	344 KB	Output is correct
18	Incorrect	0 ms	348 KB	'impossible' claimed, but there is a solution
19	Halted	0 ms	0 KB	-

Subtask #4
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	14024 KB	Output is correct
2	Correct	3 ms	2648 KB	Output is correct
3	Correct	10 ms	9304 KB	Output is correct
4	Correct	41 ms	11612 KB	Output is correct
5	Incorrect	39 ms	18448 KB	'impossible' claimed, but there is a solution
6	Halted	0 ms	0 KB	-

Subtask #5
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	424 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	600 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	344 KB	Output is correct
18	Incorrect	0 ms	348 KB	'impossible' claimed, but there is a solution
19	Halted	0 ms	0 KB	-

답안 #1067227

Compilation message

Subtask #1 0 / 13.0

Subtask #2 0 / 20.0

Subtask #3 0 / 22.0

Subtask #4 0 / 19.0

Subtask #5 0 / 26.0

Subtask #1
0 / 13.0

Subtask #2
0 / 20.0

Subtask #3
0 / 22.0

Subtask #4
0 / 19.0

Subtask #5
0 / 26.0