Submission #951567

#	Time	Username	Problem	Language	Result	Execution time	Memory
951567		mocha	Alternating Current (BOI18_alternating)	C++14	13 / 100	3015 ms	6996 KiB

alternating

#include <bits/stdc++.h>
using namespace std;
const int mx = 1e5+5;

int n, m;
int ans;

struct Edge {
	int ty;
	int fr, to;
} e[mx];

int main() {
	cin.tie(0);ios::sync_with_stdio(0);

	cin >> n >> m;
	for (int i=0;i<m;i++) {
		cin >> e[i].fr >> e[i].to;
		if (e[i].fr == e[i].to) {
			e[i].ty = 0;
		} else if (e[i].fr < e[i].to) {
			e[i].ty = 1;
		} else {
			e[i].ty = 2;
		}
	}
	bool fl = 0;
	for (int i=0;i<(1<<m);i++) {
		set<int> s[2];
		for (int j=0;j<m;j++) {
			int tp = (i&(1<<j)?1:0);
			if (e[j].ty == 0) {
				s[tp].insert(e[j].fr);
			} else if (e[j].ty == 1) {
				for (int k=e[j].fr;k<=e[j].to;k++) {
					s[tp].insert(k);
				}
			} else {
				for (int k=e[j].fr;k<=n;k++) {
					s[tp].insert(k);
				}
				for (int k=1;k<=e[j].to;k++) {
					s[tp].insert(k);
				}
			}
		}
		if (s[0].size() == n and s[1].size() == n) {
			fl = 1;
			ans = i;
			break;
		}
	}
	if (fl) {
		for (int i=0;i<m;i++) {
			cout << ((1<<i)&ans?1:0);
		}
		cout << "\n";
	} else {
		cout << "impossible\n";
	}
}

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:47:19: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |   if (s[0].size() == n and s[1].size() == n) {
      |       ~~~~~~~~~~~~^~~~
alternating.cpp:47:40: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |   if (s[0].size() == n and s[1].size() == n) {
      |                            ~~~~~~~~~~~~^~~~

• Subtask 1: 13 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 0 / 19
• Subtask 5: 0 / 26