Submission #863327

#	Time	Username	Problem	Language	Result	Execution time	Memory
863327		maks007	Alternating Current (BOI18_alternating)	C++14	13 / 100	13 ms	6356 KiB

alternating

// Bismi ALlah
#include "bits/stdc++.h"

using namespace std;

#define int long long

int lay(pair <int,int> a, int pos) {
	if(a.first <= a.second) {
		return a.first <= pos && pos <= a.second;
	}
	if(a.first <= pos) return 1;
	if(pos <= a.second) return 1;
	return 0;
}

signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m;
	vector <pair <int,int>> wrap;
	for(int i = 0; i < m; i ++) {
		int l, r;
		cin >> l >> r;
		wrap.push_back({l, r});
	}
	vector <pair <int,int>> clockwise, antiwise;
	function <int(int)> get=[&](int pos) {
		for(auto i : clockwise) {
			if(lay(i, pos)) goto end2;
		}
		return 2;
		end2:;
		for(auto i : antiwise) {
			if(lay(i, pos)) return 1;
		}
		return 0;
	};
	string ans;
	for(int mask = 0; mask < (1 << (int)wrap.size()); mask ++) {
	//int mask = 5;
		for(int i = 0; i < wrap.size(); i ++) {
			if(mask & (1 << i)) clockwise.push_back(wrap[i]), ans += '0';
			else antiwise.push_back(wrap[i]), ans += '1';
		} 
		for(int i = 1; i <= n; i ++) {
			if(get(i) == 1) continue;
			goto end;
		}
	//	reverse(ans.begin(), ans.end());
		cout << ans;
		return 0;
		end:;
		clockwise.clear();
		antiwise.clear();
		ans = "";
	}
	cout << "impossible";
	return 0;
}

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:43:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(int i = 0; i < wrap.size(); i ++) {
      |                  ~~^~~~~~~~~~~~~

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