oj.uz

Submission #417124

# Submission time Handle Problem Language Result Execution time Memory
417124 2021-06-03T11:58:38 Z maomao90 Ancient Machine (JOI21_ancient_machine) C++17
0 / 100
 594 ms 12140 KB 
#include "Anna.h"
#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb emplace_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

// might need to move this into namespace
#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 100005

namespace {
	int n;
	vector<char> s;
	vi lft;
	set<int> ys, zs, xs;
	vector<iii> ans;
	
	bool isPos(int x) {
		int ptr = 0;
		lft.clear();
		ys.clear(); zs.clear(); xs.clear();
		ans.clear();
		REP (i, 0, n) {
			if (s[i] == 'Y') ys.insert(i);
			else if (s[i] == 'Z') zs.insert(i);
			else if (s[i] == 'X') xs.insert(i);
		}
		REP (i, 0, x) {
			while (ptr < n && s[ptr] != 'X') ptr++;
			if (ptr >= n) return 0;
			lft.pb(ptr++);
		}
		REP (i, 0, x) {
			int u = lft.back();
			auto tmp = ys.lower_bound(u);
			if (tmp == ys.end()) return 0;
			int ny = *tmp;
			auto tmpp = zs.lower_bound(ny);
			if (tmpp == zs.end()) return 0;
			int nz = *tmpp;
			int py = *prev(ys.lower_bound(nz));
			int px = *prev(xs.lower_bound(py));
			auto ptr = xs.lower_bound(px);
			while (ptr != xs.end() && *ptr <= nz) {
				auto nxt = next(ptr);
				xs.erase(ptr);
				ptr = nxt;
			}
			ptr = ys.lower_bound(px);
			while (ptr != ys.end() && *ptr <= nz) {
				auto nxt = next(ptr);
				ys.erase(ptr);
				ptr = nxt;
			}
			ptr = zs.lower_bound(px);
			while (ptr != zs.end() && *ptr <= nz) {
				auto nxt = next(ptr);
				zs.erase(ptr);
				ptr = nxt;
			}
			if (px == u) {
				lft.pop_back();
			}
			ans.pb(px, py, nz);
		}
		return 1;
	}
}

void Anna(int N, vector<char> S) {
	n = N; s = S;
	REP (i, 0, n) {
		if (s[i] == 'X') {
			Send(0);
			Send(0);
		} else if (s[i] == 'Y') {
			Send(0);
			Send(1);
		} else if (s[i] == 'Z') {
			Send(1);
			Send(0);
		}
	}
	return;
	int lo = 0, hi = n / 3, mid;
	int res = -1;
	while (lo <= hi) {
		int mid = lo + hi >> 1;
		if (isPos(mid)) {
			res = mid;
			lo = mid + 1;
		} else {
			hi = mid - 1;
		}
	}
	assert(res != -1);
	assert(isPos(res));
}

#include "Bruno.h"
#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb emplace_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 200005

namespace {
	int n, l;
	vi a;
	vector<char> s;

	vi lft;
	set<int> ys, zs, xs;
	vector<iii> ans;
	
	bool isPos(int x) {
		int ptr = 0;
		lft.clear();
		ys.clear(); zs.clear(); xs.clear();
		ans.clear();
		REP (i, 0, n) {
			if (s[i] == 'Y') ys.insert(i);
			else if (s[i] == 'Z') zs.insert(i);
			else if (s[i] == 'X') xs.insert(i);
		}
		REP (i, 0, x) {
			while (ptr < n && s[ptr] != 'X') ptr++;
			if (ptr >= n) return 0;
			lft.pb(ptr++);
		}
		REP (i, 0, x) {
			int u = lft.back();
			auto tmp = ys.lower_bound(u);
			if (tmp == ys.end()) return 0;
			int ny = *tmp;
			auto tmpp = zs.lower_bound(ny);
			if (tmpp == zs.end()) return 0;
			int nz = *tmpp;
			int py = *prev(ys.lower_bound(nz));
			int px = *prev(xs.lower_bound(py));
			auto ptr = xs.lower_bound(px);
			while (ptr != xs.end() && *ptr <= nz) {
				auto nxt = next(ptr);
				xs.erase(ptr);
				ptr = nxt;
			}
			ptr = ys.lower_bound(px);
			while (ptr != ys.end() && *ptr <= nz) {
				auto nxt = next(ptr);
				ys.erase(ptr);
				ptr = nxt;
			}
			ptr = zs.lower_bound(px);
			while (ptr != zs.end() && *ptr <= nz) {
				auto nxt = next(ptr);
				zs.erase(ptr);
				ptr = nxt;
			}
			if (px == u) {
				lft.pop_back();
			}
			ans.pb(px, py, nz);
		}
		return 1;
	}
	bool solve(int x) {
		int ptr = 0;
		lft.clear();
		ys.clear(); zs.clear(); xs.clear();
		ans.clear();
		REP (i, 0, n) {
			if (s[i] == 'Y') ys.insert(i);
			else if (s[i] == 'Z') zs.insert(i);
			else if (s[i] == 'X') xs.insert(i);
		}
		REP (i, 0, x) {
			while (ptr < n && s[ptr] != 'X') ptr++;
			if (ptr >= n) return 0;
			lft.pb(ptr++);
		}
		REP (i, 0, x) {
			int u = lft.back();
			auto tmp = ys.lower_bound(u);
			if (tmp == ys.end()) return 0;
			int ny = *tmp;
			auto tmpp = zs.lower_bound(ny);
			if (tmpp == zs.end()) return 0;
			int nz = *tmpp;
			int py = *prev(ys.lower_bound(nz));
			int px = *prev(xs.lower_bound(py));
			auto ptr = xs.lower_bound(px);
			while (ptr != xs.end() && *ptr <= nz) {
				auto nxt = next(ptr);
				if (*ptr != px) {
					Remove(*ptr);
				}
				xs.erase(ptr);
				ptr = nxt;
			}
			ptr = ys.lower_bound(px);
			while (ptr != ys.end() && *ptr <= nz) {
				auto nxt = next(ptr);
				if (*ptr != py) {
					Remove(*ptr);
				}
				ys.erase(ptr);
				ptr = nxt;
			}
			ptr = zs.lower_bound(px);
			while (ptr != zs.end() && *ptr <= nz) {
				auto nxt = next(ptr);
				if (*ptr != nz) {
					Remove(*ptr);
				}
				zs.erase(ptr);
				ptr = nxt;
			}
			if (px == u) {
				lft.pop_back();
			}
			Remove(py);
			Remove(px);
			Remove(nz);
			ans.pb(px, py, nz);
		}
		for (auto i : xs) {
			Remove(i);
		}
		for (auto i : ys) {
			Remove(i);
		}
		for (auto i : zs) {
			Remove(i);
		}
		return 1;
	}
}

void Bruno(int N, int L, vi A) {
	n = N; l = L; a = A;
	REP (i, 0, n) {
		int x = a[i * 2], y = a[i * 2 + 1];
		if (x == 0) {
			if (y == 0) {
				s.pb('X');
			} else {
				s.pb('Y');
			}
		} else {
			s.pb('Z');
		}
	}
	int lo = 0, hi = n, mid;
	int res = -1;
	while (lo <= hi) {
		int mid = lo + hi >> 1;
		if (isPos(mid)) {
			res = mid;
			lo = mid + 1;
		} else {
			hi = mid - 1;
		}
	}
	assert(res != -1);
	solve(res);
}

Compilation message

Anna.cpp: In function 'void Anna(int, std::vector<char>)':
Anna.cpp:109:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |   int mid = lo + hi >> 1;
      |             ~~~^~~~
Anna.cpp:106:26: warning: unused variable 'mid' [-Wunused-variable]
  106 |  int lo = 0, hi = n / 3, mid;
      |                          ^~~

Bruno.cpp: In function 'void Bruno(int, int, vi)':
Bruno.cpp:180:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  180 |   int mid = lo + hi >> 1;
      |             ~~~^~~~
Bruno.cpp:177:22: warning: unused variable 'mid' [-Wunused-variable]
  177 |  int lo = 0, hi = n, mid;
      |                      ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 484 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Incorrect 594 ms 12140 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -