Submission #952845

#	Time	Username	Problem	Language	Result	Execution time	Memory
952845		koukirocks	Alternating Current (BOI18_alternating)	C++17	13 / 100	9 ms	604 KiB

alternating

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
 
namespace{using namespace std;}
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=15+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;

int n,m;
pii seg[MAX];

int main() {
	speed;
	cin>>n>>m;
	for (int i=0;i<m;i++) {
		cin>>seg[i].F>>seg[i].S;
	}
	int ans=-1;
	for (int s=0;s<(1<<m);s++) {
		bool cvr[MAX][2];
		memset(cvr,0,sizeof(cvr));
//		cout<<s<<"     s\n";
		for (int i=0;i<m;i++) {
			if (s&(1<<i)) {
				for (int j=seg[i].F;j!=seg[i].S;j=(j%n)+1) {
//					cout<<i<<" "<<j<<"\n";
					cvr[j][1]=true;
				}
				cvr[seg[i].S][1]=true;
			} else {
				for (int j=seg[i].S;j!=seg[i].F;j=(j+n-2)%n+1) {
//					cout<<i<<" "<<j<<"\n";
					cvr[j][0]=true;
				}
				cvr[seg[i].F][0]=true;
			}
		}
//		for (int i=1;i<=n;i++) {
//			cout<<cvr[i][0]<<" "<<cvr[i][1]<<"\n";
//		}
		bool flag=true;
		for (int i=1;i<=n;i++) {
			if (!cvr[i][0] or !cvr[i][1]) {
				flag=false;
				break;
			}
		}
		if (flag) {
			ans=s;
			break;
		}
	}
	if (ans==-1) cout<<"impossible\n";
	else {
		for (int i=0;i<m;i++) {
			if (ans&(1<<i)) cout<<"1";
			else cout<<"0";
		}
	}
	return 0;
}

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