QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#805739#2337. AzulejosSGColinAC ✓423ms44976kbC++202.3kb2024-12-08 18:16:362024-12-08 18:16:38

Judging History

This is the latest submission verdict.

  • [2024-12-08 18:16:38]
  • Judged
  • Verdict: AC
  • Time: 423ms
  • Memory: 44976kb
  • [2024-12-08 18:16:36]
  • Submitted

answer

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

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pii pair<int, int>
#define tii tuple<int, int, int>

#define N 500007

int p[N], ansb[N], anss[N];

tii b[N], s[N];

set<pii> B, S;

int main() {
	int n = rd();
	for (int i = 1; i <= n; ++i) p[i] = rd();
	for (int i = 1; i <= n; ++i) b[i] = mt(p[i], rd(), i);
	sort(b + 1, b + 1 + n);
	for (int i = 1; i <= n; ++i) p[i] = rd();
	for (int i = 1; i <= n; ++i) s[i] = mt(p[i], rd(), i);
	sort(s + 1, s + 1 + n);
	int tot = 0;
	for (int ptrs = 0, ptrb = 0; ptrs < n || ptrb < n;) {
		if (ptrs > ptrb) {
			++ptrb; 
			B.insert(mp(get<1>(b[ptrb]), get<2>(b[ptrb])));
			while (ptrb < n && get<0>(b[ptrb]) == get<0>(b[ptrb + 1])) {
				++ptrb; B.insert(mp(get<1>(b[ptrb]), get<2>(b[ptrb])));
			}
		} else if (ptrs < ptrb) {
			++ptrs; 
			S.insert(mp(get<1>(s[ptrs]), get<2>(s[ptrs])));
			while (ptrs < n && get<0>(s[ptrs]) == get<0>(s[ptrs + 1])) {
				++ptrs; S.insert(mp(get<1>(s[ptrs]), get<2>(s[ptrs])));
			}
		} else {
			++ptrb; 
			B.insert(mp(get<1>(b[ptrb]), get<2>(b[ptrb])));
			while (ptrb < n && get<0>(b[ptrb]) == get<0>(b[ptrb + 1])) {
				++ptrb; B.insert(mp(get<1>(b[ptrb]), get<2>(b[ptrb])));
			}
			++ptrs; 
			S.insert(mp(get<1>(s[ptrs]), get<2>(s[ptrs])));
			while (ptrs < n && get<0>(s[ptrs]) == get<0>(s[ptrs + 1])) {
				++ptrs; S.insert(mp(get<1>(s[ptrs]), get<2>(s[ptrs])));
			}
		}
    
		if (ptrs <= ptrb) {
			for (auto [h, id] : S) {
				if (h >= (*--B.end()).first) {puts("impossible"); return 0;}
				anss[++tot] = id; ansb[tot] = (*B.upper_bound(mp(h, 1e9))).second;
				B.erase(B.upper_bound(mp(h, 1e9))); 
			}
			S.clear();
		} else {
			for (auto [h, id] : B) {
				if (h <= (*S.begin()).first) {puts("impossible"); return 0;}
				ansb[++tot] = id; anss[tot] = (*--S.lower_bound(mp(h, 0))).second;
				S.erase(--S.lower_bound(mp(h, 0)));
			}
			B.clear();
		}
	}
	for (int i = 1; i <= n; ++i) printf("%d ", ansb[i]); puts("");
	for (int i = 1; i <= n; ++i) printf("%d ", anss[i]);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 9932kb

Test #2:

score: 0
Accepted
time: 1ms
memory: 7804kb

Test #3:

score: 0
Accepted
time: 0ms
memory: 12052kb

Test #4:

score: 0
Accepted
time: 1ms
memory: 7760kb

Test #5:

score: 0
Accepted
time: 0ms
memory: 12156kb

Test #6:

score: 0
Accepted
time: 1ms
memory: 7816kb

Test #7:

score: 0
Accepted
time: 1ms
memory: 11996kb

Test #8:

score: 0
Accepted
time: 0ms
memory: 10012kb

Test #9:

score: 0
Accepted
time: 1ms
memory: 12092kb

Test #10:

score: 0
Accepted
time: 0ms
memory: 11704kb

Test #11:

score: 0
Accepted
time: 1ms
memory: 11972kb

Test #12:

score: 0
Accepted
time: 220ms
memory: 44976kb

Test #13:

score: 0
Accepted
time: 0ms
memory: 12156kb

Test #14:

score: 0
Accepted
time: 1ms
memory: 10032kb

Test #15:

score: 0
Accepted
time: 0ms
memory: 12616kb

Test #16:

score: 0
Accepted
time: 0ms
memory: 11976kb

Test #17:

score: 0
Accepted
time: 1ms
memory: 12044kb

Test #18:

score: 0
Accepted
time: 2ms
memory: 12028kb

Test #19:

score: 0
Accepted
time: 0ms
memory: 12100kb

Test #20:

score: 0
Accepted
time: 1ms
memory: 12048kb

Test #21:

score: 0
Accepted
time: 1ms
memory: 11912kb

Test #22:

score: 0
Accepted
time: 46ms
memory: 16908kb

Test #23:

score: 0
Accepted
time: 40ms
memory: 18684kb

Test #24:

score: 0
Accepted
time: 59ms
memory: 19736kb

Test #25:

score: 0
Accepted
time: 30ms
memory: 15220kb

Test #26:

score: 0
Accepted
time: 168ms
memory: 44540kb

Test #27:

score: 0
Accepted
time: 30ms
memory: 19876kb

Test #28:

score: 0
Accepted
time: 49ms
memory: 21536kb

Test #29:

score: 0
Accepted
time: 34ms
memory: 21456kb

Test #30:

score: 0
Accepted
time: 33ms
memory: 19744kb

Test #31:

score: 0
Accepted
time: 423ms
memory: 44820kb

Test #32:

score: 0
Accepted
time: 56ms
memory: 20884kb

Test #33:

score: 0
Accepted
time: 308ms
memory: 44864kb