oj.uz

Submission #386813

# Submission time Handle Problem Language Result Execution time Memory
386813 2021-04-07T11:00:02 Z maximath_1 Alternating Current (BOI18_alternating) C++11
19 / 100
 88 ms 14568 KB 
#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 i = 1; i <= n; i ++)
		vis[i][0] = vis[i][1] = 0;

	for(int i = 1; i <= n; i ++){
		int gt = i;
		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

alternating.cpp: In function 'int main()':
alternating.cpp:110:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Correct 6 ms 7404 KB Output is correct
4 Correct 5 ms 7532 KB Output is correct
5 Incorrect 5 ms 7404 KB 'impossible' claimed, but there is a solution
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Correct 6 ms 7404 KB Output is correct
4 Correct 5 ms 7532 KB Output is correct
5 Incorrect 5 ms 7404 KB 'impossible' claimed, but there is a solution
6 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Correct 6 ms 7404 KB Output is correct
4 Correct 5 ms 7532 KB Output is correct
5 Incorrect 5 ms 7404 KB 'impossible' claimed, but there is a solution
6 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 14568 KB Output is correct
2 Correct 6 ms 7404 KB Output is correct
3 Correct 23 ms 9708 KB Output is correct
4 Correct 33 ms 12140 KB Output is correct
5 Correct 57 ms 11244 KB Output is correct
6 Correct 49 ms 11244 KB Output is correct
7 Correct 51 ms 11372 KB Output is correct
8 Correct 7 ms 7532 KB Output is correct
9 Correct 6 ms 7404 KB Output is correct
10 Correct 56 ms 11372 KB Output is correct
11 Correct 43 ms 10604 KB Output is correct
12 Correct 52 ms 11756 KB Output is correct
13 Correct 6 ms 7404 KB Output is correct
14 Correct 6 ms 7404 KB Output is correct
15 Correct 57 ms 10988 KB Output is correct
16 Correct 32 ms 12140 KB Output is correct
17 Correct 88 ms 13420 KB Output is correct
18 Correct 80 ms 12652 KB Output is correct
19 Correct 8 ms 7660 KB Output is correct
20 Correct 48 ms 10604 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Correct 6 ms 7404 KB Output is correct
4 Correct 5 ms 7532 KB Output is correct
5 Incorrect 5 ms 7404 KB 'impossible' claimed, but there is a solution
6 Halted 0 ms 0 KB -