QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#131699#4676. Amalgamated ArtichokesPetroTarnavskyi#RE 0ms0kbC++174.4kb2023-07-27 21:41:292023-07-27 21:41:31

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-27 21:41:31]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-07-27 21:41:29]
  • 提交

answer

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

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FILL(a, b) memset(a, b, sizeof(a))

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

const int INF = 1e9 + 47;
const int N = 1 << 8;

#define begin beg
#define end en

int maxCoord[2];
bool active[N];
int begin[N][2], end[N][2];

bool intersect(int i, int j, int t) {
	return max(begin[i][t], begin[j][t]) <= min(end[i][t], end[j][t]);
}

bool intersect(int i, int j) {
	FOR(t, 0, 2) {
		if (!intersect(i, j, t)) {
			return false;
		}
	}
	return true;
}

int n = 0;

bool openWindow(int x, int y, int w, int h, int j) {
	begin[n][0] = x;
	begin[n][1] = y;
	end[n][0] = x + w - 1;
	end[n][1] = y + h - 1;
	if (end[n][0] >= maxCoord[0] && end[n][1] >= maxCoord[1]) {
		return false;
	}
	FOR(i, 0, n) {
		if (i != j && active[i] && intersect(i, n)) {
			return false;
		}
	}
	return true;
}

int findWindow(int x, int y) {
	FOR(i, 0, n) {
		if (active[i] && begin[i][0] <= x && x <= end[i][0] && begin[i][1] <= y && y <= end[i][1]) {
			return i;
		}
	}
	return -1;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	FOR(i, 0, 2) {
		cin >> maxCoord[i];
	}
	string s;
	int command = 1;
	int cntActive = 0;
	while (cin >> s) {
		if (s == "OPEN") {
			int x, y, w, h;
			cin >> x >> y >> w >> h;
			active[n] = openWindow(x, y, w, h, -1);
			if (!active[n]) {
				cout << "Command " << command << ": OPEN - window does not fit\n";
			}
			else {
				n++;
				cntActive++;
			}
		}
		else if (s == "CLOSE") {
			int x, y;
			cin >> x >> y;
			int idx = findWindow(x, y);
			if (idx == -1) {
				cout << "Command " << command << ": CLOSE - no window at given position\n";
			}
			else {
				active[idx] = false;
				cntActive--;
			}
		}
		else if (s == "RESIZE") {
			int x, y, w, h;
			cin >> x >> y >> w >> h;
			int idx = findWindow(x, y);
			if (idx == -1) {
				cout << "Command " << command << ": RESIZE - no window at given position\n";
			}
			else if (!openWindow(begin[idx][0], begin[idx][1], w, h, idx)) {
					cout << "Command " << command << ": RESIZE - window does not fit\n";
			}
			else {
				end[idx][0] = begin[idx][0] + w - 1;
				end[idx][1] = begin[idx][1] + h - 1;
			}
		}
		else {
			assert(s == "MOVE");
			int x, y, dx, dy;
			cin >> x >> y >> dx >> dy;
			int idx = findWindow(x, y);
			if (idx == -1) {
				cout << "Command " << command << ": MOVE - no window at given position\n";
			}
			else {
				int t = dy != 0 ? 1 : 0;
				int d = abs(dx + dy);
				if (dx + dy < 0) {
					FOR(i, 0, n) {
						begin[i][t] = maxCoord[t] - 1 - begin[i][t];
						end[i][t] = maxCoord[t] - 1 - end[i][t];
						swap(begin[i][t], end[i][t]);
					}
				}
				vector<int> vec, inVec(n, 0), mn(n, INF);
				vec.push_back(idx);
				inVec[idx] = 1;
				int moved = 0;
				while (true) {
					int globalMn = INF, indexMn = -1;
					FOR(i, 0, n) {
						if (active[i] && !inVec[i] && intersect(idx, i, t ^ 1)) {
							mn[i] = min(mn[i], begin[i][t] - end[idx][t] - 1);
							if (mn[i] < d - moved && mn[i] < globalMn) {
								globalMn = mn[i];
								indexMn = i;
							}
						}
					}
					int currentMove;
					if (indexMn == -1) {
						currentMove = min(d, maxCoord[t] - 1 - end[idx][t]);
					}
					else {
						currentMove = globalMn;
					}
					for (int i: vec) {
						begin[i][t] += currentMove;
						end[i][t] += currentMove;
					}
					moved += currentMove;
					FOR(i, 0, n) {
						mn[i] -= currentMove;
					}
					if (indexMn == -1) {
						break;
					}
					else {
						idx = indexMn;
					}
				}
				if (dx + dy < 0) {
					FOR(i, 0, n) {
						begin[i][t] = maxCoord[t] - 1 - begin[i][t];
						end[i][t] = maxCoord[t] - 1 - end[i][t];
						swap(begin[i][t], end[i][t]);
					}
				}
				if (moved < d) {
					cout << "Command " << command << ": MOVE - moved " << moved << " instead of " << d << "\n";
				}
			}
		}
		command++;
	}
	cout << cntActive << " window(s):\n";
	FOR(i, 0, n) {
		if (active[i]) {
			cout << begin[i][0] << " " << begin[i][1] << " " << end[i][0] - begin[i][0] + 1 << " " << end[i][1] - begin[i][1] + 1 << "\n";
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

input:

42 1 23 4 8 10

output:


result: