Submission #386814

#	Time	Username	Problem	Language	Result	Execution time	Memory
386814		maximath_1	Alternating Current (BOI18_alternating)	C++11	74 / 100	3074 ms	14568 KiB

alternating

#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <numeric>
#include <iostream>
#include <queue>
#include <assert.h>
#include <map>
#include <set>
#include <limits.h>
#include <random>
#include <chrono>
using namespace std;
 
#define ll long long
#define ld long double
const int MX = 300005;
const int BLOCK = 105;
const ll inf = 8000000000000000069ll;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
const int dxh[] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dyh[] = {2, -2, 2, -2, 1, -1, 1, -1}; // horse
const int dx[] = {1, -1, 0, 0, 0, 0};
const int dy[] = {0, 0, 1, -1, 0, 0}; // adj
const int dz[] = {0, 0, 0, 0, 1, -1};
const int dxd[] = {1, 1, 1, 0, -1, -1, -1, 0};
const int dyd[] = {1, 0, -1, -1, -1, 0, 1, 1}; // diag

mt19937 rng(time(NULL));

int n, m;
vector<pair<pair<int, int>, int> > v;

void imp(){
	cout << "impossible\n";
	exit(0);
}

int dist(int x, int y){
	int get = y + n - x + 1;
	if(get > n) get -= n;
	return get;
}

void solve(){
	set<pair<int, int> > s;
	vector<int> ans(m + 1, 0);

	int c1 = 0, c2 = 0;
	for(int j = 0, i = 1; i <= n; i ++){
		for(; j < m && v[j].first.first == i; j ++)
			s.insert(make_pair(v[j].first.second, v[j].second));
		for(; s.size() && s.begin() -> first < i;)
			s.erase(s.begin());

		if(c1 < i){
			if(s.empty()) imp();
			c1 = s.begin() -> first;
			ans[s.begin() -> second] = 1;
			s.erase(s.begin());
		}

		if(c2 < i){
			if(s.empty()) imp();
			c2 = s.begin() -> first;
			ans[s.begin() -> second] = 0;
			s.erase(s.begin());
		}
	}

	for(int i = 0; i < m; i ++)
		cout << ans[i];
	exit(0);
}

vector<pair<int, int> > adj[MX];
int vis[MX][2];

int main(){
	cin.tie(0) -> sync_with_stdio(0);
	cin >> n >> m;
	v.resize(m);

	bool aa = 1;
	for(int i = 0; i < m; i ++){
		cin >> v[i].first.first >> v[i].first.second;
		if(v[i].first.first > v[i].first.second) aa = 0;
		v[i].second = i;
	}
	for(int i = 0; i < m; i ++)
		adj[v[i].first.first].emplace_back(dist(v[i].first.first, v[i].first.second), i);

	sort(v.begin(), v.end());

	if(aa) solve();

	int c1 = 0, c2 = 0;
	vector<int> ans(m);

	for(int offset = 0; offset < n; offset ++){
		for(int i = 1; i <= n; i ++)
			vis[i][0] = vis[i][1] = 0;

		for(int i = 1; i <= n; i ++){
			int gt = i + offset;
			if(gt > n) gt -= n;
			for(int j = 0; j < adj[gt].size(); j ++){
				int x = adj[gt][j].first;
				for(int k = 0; k < n; k ++){
					int nw = gt + k;
					if(nw > n) nw -= n;

					if(vis[nw][0] == 0){
						ans[adj[gt][j].second] = 0;
						break;
					}
					if(vis[nw][1] == 0){
						ans[adj[gt][j].second] = 1;
						break;
					}
				}

				for(int l = 0; l < x; l ++){
					int cr = gt + l;
					if(cr > n) cr -= n;
					vis[cr][ans[adj[gt][j].second]] = 1;
				}
			}
		}

		bool ok = 1;
		for(int i = 1; i <= n; i ++)
			if(vis[i][0] == 0 || vis[i][1] == 0)
				ok = 0;
		
		if(ok){
			for(int i = 0; i < m; i ++)
				cout << ans[i];
			cout << endl;
			exit(0);
		}
	}

	imp();
	return 0;
}

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:111:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |    for(int j = 0; j < adj[gt].size(); j ++){
      |                   ~~^~~~~~~~~~~~~~~~
alternating.cpp:101:6: warning: unused variable 'c1' [-Wunused-variable]
  101 |  int c1 = 0, c2 = 0;
      |      ^~
alternating.cpp:101:14: warning: unused variable 'c2' [-Wunused-variable]
  101 |  int c1 = 0, c2 = 0;
      |              ^~

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