QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#131723 | #4688. Window Manager | PetroTarnavskyi# | WA | 1ms | 3608kb | C++17 | 4.9kb | 2023-07-27 22:22:02 | 2023-07-27 22:22:05 |
Judging History
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 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] >= 0 && mn[i] < d - moved && mn[i] < globalMn) {
globalMn = mn[i];
indexMn = i;
}
}
}
//cerr << "globalMn " << globalMn << endl;
//cerr << "indexMn " << indexMn << endl;
int maxEnd = -1;
for (int i : vec) {
maxEnd = max(maxEnd, end[i][t]);
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3476kb
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: 3476kb
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: 3584kb
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: 3468kb
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: 1ms
memory: 3540kb
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: 1ms
memory: 3488kb
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: 3540kb
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: 1ms
memory: 3476kb
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: 3464kb
input:
320 200
output:
0 window(s):
result:
ok single line: '0 window(s):'
Test #10:
score: -100
Wrong Answer
time: 1ms
memory: 3608kb
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'