Submission #126948

#	Time	Username	Problem	Language	Result	Execution time	Memory
126948		mechfrog88	Alternating Current (BOI18_alternating)	C++14	13 / 100	3031 ms	1048576 KiB

alternating

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;
 
vector <pair<ll,ll>> arr;
vector <bool> ans;
ll n,m;

void func(ll index,vector <bool> temp){
	if (index == m){
		vector <pair<bool,bool>> seg(n+1);
		for (int z=0;z<=n;z++){
			seg[z].first = false;
			seg[z].second = false;
		}
		for (int z=0;z<temp.size();z++){
			if (temp[z]){
				ll l = arr[z].first;
				ll r = arr[z].second;
				seg[r].first = true;
				while (l != r){
					seg[l].first = true;
					l++;
					if (l == n+1){
						l = 1;
					}
				}
			} else {
				ll l = arr[z].first;
				ll r = arr[z].second;
				seg[r].second = true;
				while (l != r){
					seg[l].second = true;
					l++;
					if (l == n+1){
						l = 1;
					}
				}
			}
		}
		bool ok = true;
		for (int z=1;z<=n;z++){
			if (!seg[z].first || !seg[z].second){
				ok = false;
			}
		}
		if (ok){
			ans = temp;
		}
		return;
	}
	temp[index] = 0;
	func(index+1,temp);
	temp[index] = 1;
	func(index+1,temp);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	arr.resize(m);
	for (int z=0;z<m;z++){
		cin >> arr[z].first >> arr[z].second;
	}
	vector <bool> temp(m);
	func(0,temp);
	if (ans.size() == 0){
		cout << "impossible" << endl;
	} else {
		for (bool i : ans){
			cout << i ;
		} cout << endl;
	}
	
}

Compilation message (stderr)

alternating.cpp: In function 'void func(ll, std::vector<bool>)':
alternating.cpp:27:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int z=0;z<temp.size();z++){
                ~^~~~~~~~~~~~

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