QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#131734#4688. Window ManagerPetroTarnavskyiWA 1ms3592kbC++174.9kb2023-07-27 22:37:132023-07-27 22:37:14

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 22:37:14]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3592kb
  • [2023-07-27 22:37:13]
  • 提交

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 << 9;

#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 {
			//cerr << "s = " << s << endl;
			assert(s == "MOVE");
			//cerr << "command MOVE\n";
			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;
				//cerr << "idx = " << idx << endl;
				while (true) {
					int maxEnd = -1;
					for (int i : vec) {
						maxEnd = max(maxEnd, end[i][t]);
					}
					int globalMn = INF, indexMn = -1;
					FOR(i, 0, n) {
						if (active[i] && !inVec[i] && intersect(idx, i, t ^ 1)) {
							if(begin[i][t] - end[idx][t] - 1 >= 0)
								mn[i] = min(mn[i], begin[i][t] - end[idx][t] - 1);
							if (mn[i] >= 0 && mn[i] < d - moved && mn[i] < globalMn) {
								globalMn = mn[i];
								indexMn = i;
							}
						}
					}
					//cerr << "globalMn " << globalMn << endl;
					//cerr << "indexMn " << indexMn << endl;
					int currentMove;
					if (indexMn == -1) {
						currentMove = min(d - moved, maxCoord[t] - 1 - maxEnd);
					}
					else {
						currentMove = globalMn;
					}
					//cerr << "currentMove " << currentMove << endl;
					for (int i: vec) {
						begin[i][t] += currentMove;
						end[i][t] += currentMove;
						assert(end[i][t] < maxCoord[t]);
					}
					moved += currentMove;
					FOR(i, 0, n) {
						mn[i] -= currentMove;
					}
					if (indexMn == -1) {
						break;
					}
					else {
						idx = indexMn;
						vec.push_back(idx);
						inVec[idx] = 1;
					}
				}
				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;
}

详细

Test #1:

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

input:

320 200
OPEN 50 50 10 10
OPEN 70 55 10 10
OPEN 90 50 10 10
RESIZE 55 55 40 40
RESIZE 55 55 15 15
MOVE 55 55 40 0
CLOSE 55 55
CLOSE 110 60
MOVE 95 55 0 -100

output:

Command 4: RESIZE - window does not fit
Command 7: CLOSE - no window at given position
Command 9: MOVE - moved 50 instead of 100
2 window(s):
90 0 15 15
115 50 10 10

result:

ok 6 lines

Test #2:

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

input:

10 10
OPEN 0 0 8 8
MOVE 0 0 5 0

output:

Command 2: MOVE - moved 2 instead of 5
1 window(s):
2 0 8 8

result:

ok 3 lines

Test #3:

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

input:

10 10
OPEN 2 2 8 8
MOVE 3 3 -5 0

output:

Command 2: MOVE - moved 2 instead of 5
1 window(s):
0 2 8 8

result:

ok 3 lines

Test #4:

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

input:

10 10
OPEN 2 2 8 8
MOVE 3 3 0 -5

output:

Command 2: MOVE - moved 2 instead of 5
1 window(s):
2 0 8 8

result:

ok 3 lines

Test #5:

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

input:

10 10
OPEN 0 0 8 8
MOVE 0 0 0 5

output:

Command 2: MOVE - moved 2 instead of 5
1 window(s):
0 2 8 8

result:

ok 3 lines

Test #6:

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

input:

6000 6000
OPEN 5000 5000 5 5
OPEN 5000 4990 5 5
OPEN 5000 4980 5 5
OPEN 5000 4970 5 5
OPEN 5000 4960 5 5
OPEN 5000 4950 5 5
OPEN 5000 4940 5 5
OPEN 5000 4930 5 5
OPEN 5000 4920 5 5
OPEN 5000 4910 5 5
OPEN 5000 4900 5 5
OPEN 5000 4890 5 5
OPEN 5000 4880 5 5
OPEN 5000 4870 5 5
OPEN 5000 4860 5 5
OPEN ...

output:

200 window(s):
5000 1000 5 5
5000 995 5 5
5000 990 5 5
5000 985 5 5
5000 980 5 5
5000 975 5 5
5000 970 5 5
5000 965 5 5
5000 960 5 5
5000 955 5 5
5000 950 5 5
5000 945 5 5
5000 940 5 5
5000 935 5 5
5000 930 5 5
5000 925 5 5
5000 920 5 5
5000 915 5 5
5000 910 5 5
5000 905 5 5
5000 900 5 5
5000 895 5 ...

result:

ok 201 lines

Test #7:

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

input:

1000 1000
OPEN 0 0 10 10
OPEN 10 0 10 10
OPEN 20 0 10 10
OPEN 0 10 10 10
OPEN 10 10 10 10
OPEN 20 10 10 10
OPEN 0 20 10 10
OPEN 10 20 10 10
OPEN 20 20 10 10
CLOSE 19 19
CLOSE 20 20
CLOSE 0 10

output:

6 window(s):
0 0 10 10
10 0 10 10
20 0 10 10
20 10 10 10
0 20 10 10
10 20 10 10

result:

ok 7 lines

Test #8:

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

input:

1000 1000
OPEN 500 500 10 10
CLOSE 499 499
CLOSE 499 500
CLOSE 500 499
CLOSE 510 509
CLOSE 509 510
CLOSE 510 510
CLOSE 499 510
CLOSE 500 510
CLOSE 499 509
CLOSE 510 499
CLOSE 510 500
CLOSE 509 499

output:

Command 2: CLOSE - no window at given position
Command 3: CLOSE - no window at given position
Command 4: CLOSE - no window at given position
Command 5: CLOSE - no window at given position
Command 6: CLOSE - no window at given position
Command 7: CLOSE - no window at given position
Command 8: CLOSE -...

result:

ok 14 lines

Test #9:

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

input:

320 200

output:

0 window(s):

result:

ok single line: '0 window(s):'

Test #10:

score: -100
Wrong Answer
time: 1ms
memory: 3592kb

input:

1048576 1048576
OPEN 0 0 100 1048576
OPEN 1000 0 100 524288
OPEN 1000 524288 100 524288
OPEN 2000 0 100 262144
OPEN 2000 262144 100 262144
OPEN 2000 524288 100 262144
OPEN 2000 786432 100 262144
OPEN 3000 0 100 131072
OPEN 3000 131072 100 131072
OPEN 3000 262144 100 131072
OPEN 3000 393216 100 13107...

output:

Command 128: MOVE - moved 1047876 instead of 1048576
127 window(s):
1047876 0 100 1048576
1047976 0 100 524288
1000 524288 100 524288
1048076 0 100 262144
2000 262144 100 262144
2000 524288 100 262144
2000 786432 100 262144
1048176 0 100 131072
3000 131072 100 131072
3000 262144 100 131072
3000 3932...

result:

wrong answer 5th lines differ - expected: '1047976 524288 100 524288', found: '1000 524288 100 524288'