oj.uz

Submission #417344

# Submission time Handle Problem Language Result Execution time Memory
417344 2021-06-03T15:00:49 Z maomao90 Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 751 ms 14684 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;

#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) {
			auto tmp = ys.begin(), tmpp = zs.begin();
			int u, ny, nz;
			while (1) {
				if (lft.empty()) return 0;
				u = lft.back();
				tmp = ys.lower_bound(u);
				if (tmp == ys.end()) {
					lft.pop_back();
					continue;
				}
				ny = *tmp;
				tmpp = zs.lower_bound(ny);
				if (tmpp == zs.end()) {
					lft.pop_back();
					continue;
				}
				nz = *tmpp;
				//found = 1;
				break;
			}
			int py = *prev(ys.lower_bound(nz));
			int px = *prev(xs.lower_bound(py));
			auto ptr = next(xs.lower_bound(px));
			while (ptr != xs.end() && *ptr < nz) {
				auto nxt = next(ptr);
				if (*ptr != px) {
				}
				xs.erase(ptr);
				ptr = nxt;
			}
			ptr = ys.lower_bound(px);
			while (ptr != ys.end() && *ptr < nz) {
				auto nxt = next(ptr);
				if (*ptr != py) {
				}
				ys.erase(ptr);
				ptr = nxt;
			}
			ptr = zs.lower_bound(px);
			while (ptr != zs.end() && *ptr < nz) {
				auto nxt = next(ptr);
				if (*ptr != nz) {
				}
				zs.erase(ptr);
				ptr = nxt;
			}
			ans.pb(px, py, nz);
		}
		for (auto i : xs) {
		}
		for (auto i : ys) {
		}
		for (auto i : zs) {
		}
		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) {
			auto tmp = ys.begin(), tmpp = zs.begin();
			int u, ny, nz;
			while (1) {
				if (lft.empty()) return 0;
				u = lft.back();
				tmp = ys.lower_bound(u);
				if (tmp == ys.end()) {
					lft.pop_back();
					continue;
				}
				ny = *tmp;
				tmpp = zs.lower_bound(ny);
				if (tmpp == zs.end()) {
					lft.pop_back();
					continue;
				}
				nz = *tmpp;
				//found = 1;
				break;
			}
			int py = *prev(ys.lower_bound(nz));
			int px = *prev(xs.lower_bound(py));
			auto ptr = next(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;
			}
			Remove(py);
			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:108:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |   int mid = lo + hi >> 1;
      |             ~~~^~~~
Anna.cpp:105:26: warning: unused variable 'mid' [-Wunused-variable]
  105 |  int lo = 0, hi = n / 3, mid;
      |                          ^~~

Bruno.cpp: In function 'bool {anonymous}::isPos(int)':
Bruno.cpp:104:13: warning: unused variable 'i' [-Wunused-variable]
  104 |   for (auto i : xs) {
      |             ^
Bruno.cpp:106:13: warning: unused variable 'i' [-Wunused-variable]
  106 |   for (auto i : ys) {
      |             ^
Bruno.cpp:108:13: warning: unused variable 'i' [-Wunused-variable]
  108 |   for (auto i : zs) {
      |             ^
Bruno.cpp: In function 'void Bruno(int, int, vi)':
Bruno.cpp:210:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  210 |   int mid = lo + hi >> 1;
      |             ~~~^~~~
Bruno.cpp:207:22: warning: unused variable 'mid' [-Wunused-variable]
  207 |  int lo = 0, hi = n, mid;
      |                      ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 480 KB Output is correct
2 Correct 0 ms 484 KB Output is correct
3 Correct 1 ms 500 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 484 KB Output is correct
6 Correct 2 ms 484 KB Output is correct
7 Correct 0 ms 492 KB Output is correct
8 Correct 0 ms 492 KB Output is correct
9 Correct 0 ms 484 KB Output is correct
10 Correct 0 ms 484 KB Output is correct
11 Correct 0 ms 484 KB Output is correct

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Partially correct 704 ms 12000 KB Partially correct
2 Partially correct 733 ms 12008 KB Partially correct
3 Partially correct 694 ms 12052 KB Partially correct
4 Partially correct 705 ms 12016 KB Partially correct
5 Partially correct 713 ms 11968 KB Partially correct
6 Partially correct 662 ms 12024 KB Partially correct
7 Partially correct 660 ms 12040 KB Partially correct
8 Partially correct 626 ms 11924 KB Partially correct
9 Partially correct 651 ms 12016 KB Partially correct
10 Partially correct 706 ms 12008 KB Partially correct
11 Partially correct 705 ms 12076 KB Partially correct
12 Partially correct 751 ms 11972 KB Partially correct
13 Partially correct 663 ms 11292 KB Partially correct
14 Incorrect 505 ms 14684 KB Wrong Answer [6]
15 Halted 0 ms 0 KB -