QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#131699 | #4676. Amalgamated Artichokes | PetroTarnavskyi# | RE | 0ms | 0kb | C++17 | 4.4kb | 2023-07-27 21:41:29 | 2023-07-27 21:41:31 |
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 << 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