QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#259648#2337. AzulejosnoomptyAC ✓558ms102812kbC++174.6kb2023-11-21 09:20:432023-11-21 09:20:44

Judging History

This is the latest submission verdict.

  • [2023-11-21 09:20:44]
  • Judged
  • Verdict: AC
  • Time: 558ms
  • Memory: 102812kb
  • [2023-11-21 09:20:43]
  • Submitted

answer

#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <cmath>
#include <random>
#include <string>
#include <cassert>
#include <climits>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;

#define ll long long
#define f first
#define s second

void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template<typename A> void __print(const A &x);
template<typename A, typename B> void __print(const pair<A, B> &p);
template<typename... A> void __print(const tuple<A...> &t);
template<typename T> void __print(stack<T> s);
template<typename T> void __print(queue<T> q);
template<typename T, typename... U> void __print(priority_queue<T, U...> q);

template<typename A> void __print(const A &x) {
    bool first = true;
    cerr << '{';
    for (const auto &i : x) {
        cerr << (first ? "" : ","), __print(i);
        first = false;
    }
    cerr << '}';
}

template<typename A, typename B> void __print(const pair<A, B> &p) {
    cerr << '(';
    __print(p.f);
    cerr << ',';
    __print(p.s);
    cerr << ')';
}

template<typename... A> void __print(const tuple<A...> &t) {
    bool first = true;
    cerr << '(';
    apply([&first] (const auto &...args) { ((cerr << (first ? "" : ","), __print(args), first = false), ...); }, t);
    cerr << ')';
}

template<typename T> void __print(stack<T> s) {
    vector<T> debugVector;
    while (!s.empty()) {
        T t = s.top();
        debugVector.push_back(t);
        s.pop();
    }
    reverse(debugVector.begin(), debugVector.end());
    __print(debugVector);
}

template<typename T> void __print(queue<T> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.front();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}

template<typename T, typename... U> void __print(priority_queue<T, U...> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.top();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}

void _print() { cerr << "]\n"; }

template <typename Head, typename... Tail> void _print(const Head &H, const Tail &...T) {
    __print(H);
    if (sizeof...(T)) cerr << ", ";
    _print(T...);
}

#ifdef DEBUG
	#define D(...) cerr << "Line: " << __LINE__ << " [" << #__VA_ARGS__ << "] = ["; _print(__VA_ARGS__)
#else
	#define D(...)
#endif

struct Tile {
	int p, s, idx;

	bool operator < (const Tile &t) const {
		return s < t.s;
	}
};

int n;
vector<multiset<Tile>> s[2];
vector<Tile> t;
vector<int> ans[2];

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for (int r = 0; r < 2; r++) {
		t.resize(n);
		for (int i = 0; i < n; i++) {
			cin >> t[i].p;
		}
		for (int i = 0; i < n; i++) {
			cin >> t[i].s;
		}
		for (int i = 0; i < n; i++) {
			t[i].idx = i + 1;
		}
		sort(t.begin(), t.end(), [] (const Tile &a, const Tile &b) -> bool {
			return a.p < b.p;
		});
		for (int i = 0; i < n; i++) {
			if (!i || t[i - 1].p != t[i].p) {
				s[r].emplace_back();
			}
			s[r].back().insert(t[i]);
		}
	}

	for (int idx1 = 0, idx2 = 0; ans[0].size() < n;) {
		if (s[0][idx1].size() < s[1][idx2].size()) {
			for (auto t : s[0][idx1]) {
				multiset<Tile>::iterator it = s[1][idx2].upper_bound(Tile{t.p, t.s - 1, t.idx});
				if (it == s[1][idx2].begin()) {
					cout << "impossible\n";
					exit(0);
				}
				it--;
				ans[0].push_back(t.idx);
				ans[1].push_back(it->idx);
				s[1][idx2].erase(it);
			}
			idx1++;
		} else {
			for (auto t : s[1][idx2]) {
				multiset<Tile>::iterator it = s[0][idx1].upper_bound(t);
				if (it == s[0][idx1].end()) {
					cout << "impossible\n";
					exit(0);
				}
				ans[0].push_back(it->idx);
				ans[1].push_back(t.idx);
				s[0][idx1].erase(it);
			}
			idx2++;
			if (s[0][idx1].empty()) idx1++;
		}
	}

	for (int r = 0; r < 2; r++) {
		for (int i = 0; i < ans[r].size(); i++) {
			cout << ans[r][i] << " ";
		}
		cout << "\n";
	}

}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3576kb

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

score: 0
Accepted
time: 227ms
memory: 94824kb

Test #13:

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

Test #14:

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

Test #15:

score: 0
Accepted
time: 3ms
memory: 5112kb

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

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

Test #20:

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

Test #21:

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

Test #22:

score: 0
Accepted
time: 57ms
memory: 17892kb

Test #23:

score: 0
Accepted
time: 60ms
memory: 16620kb

Test #24:

score: 0
Accepted
time: 71ms
memory: 17792kb

Test #25:

score: 0
Accepted
time: 41ms
memory: 19152kb

Test #26:

score: 0
Accepted
time: 189ms
memory: 94824kb

Test #27:

score: 0
Accepted
time: 39ms
memory: 21480kb

Test #28:

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

Test #29:

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

Test #30:

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

Test #31:

score: 0
Accepted
time: 558ms
memory: 102752kb

Test #32:

score: 0
Accepted
time: 74ms
memory: 23016kb

Test #33:

score: 0
Accepted
time: 420ms
memory: 102812kb