QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#375197 | #4688. Window Manager | InfinityNS# | WA | 1ms | 3808kb | C++14 | 5.3kb | 2024-04-02 23:15:02 | 2024-04-02 23:15:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int W,H;
char cmd[10];
struct Window{
int x,y,w,h;
Window(int a,int b,int c,int d):x(a),y(b),w(c),h(d){}
bool Inside(int a,int b){
return x<=a && x+w>a && y<=b && y+h>b;
}
bool OverlapX(Window other){
return max(x,other.x)<min(x+w,other.x+other.w);
}
bool OverlapY(Window other){
return max(y,other.y)<min(y+h,other.y+other.h);
}
bool Overlap(Window other){
return max(x,other.x)<min(x+w,other.x+other.w) &&
max(y,other.y)<min(y+h,other.y+other.h);
}
bool CheckX(Window other,int sgn){
if(sgn==-1)return other.CheckX(*this,1);
return x+w==other.x && max(y,other.y)<min(y+h,other.y+other.h);
}
bool CheckY(Window other,int sgn){
if(sgn==-1)return other.CheckY(*this,1);
return y+h==other.y && max(x,other.x)<min(x+w,other.x+other.w);
}
};
vector<Window> windows;
int Find(int x,int y){
for(int i=0;i<windows.size();i++){
if(windows[i].Inside(x,y)){
return i;
}
}
return -1;
}
void Add(Window w,int idx){
for(int i=0;i<windows.size();i++){
if(w.Overlap(windows[i])){
printf("Command %i: OPEN - window does not fit\n",idx);
return;
}
}
if(w.x+w.w>=W || w.y+w.h>=H){
printf("Command %i: OPEN - window does not fit\n",idx);
return;
}
windows.pb(w);
}
void Resize(int x,int y,int w,int h,int idx){
int j=Find(x,y);
if(j==-1){
printf("Command %i: RESIZE - no window at given position\n",idx);
return;
}
Window win=Window(windows[j].x,windows[j].y,w,h);
for(int i=0;i<windows.size();i++){
if(i==j)continue;
if(win.Overlap(windows[i])){
printf("Command %i: RESIZE - window does not fit\n",idx);
return;
}
}
if(win.x+win.w>=W || win.y+win.h>=H){
printf("Command %i: RESIZE - window does not fit\n",idx);
return;
}
windows[j]=win;
}
void Close(int x,int y,int idx){
int j=Find(x,y);
if(j==-1){
printf("Command %i: CLOSE - no window at given position\n",idx);
return;
}
for(int i=j;i+1<windows.size();i++){
windows[i]=windows[i+1];
}
windows.pop_back();
}
void Move(int x,int y,int dx,int dy,int idx){
int j=Find(x,y);
if(j==-1){
printf("Command %i: MOVE - no window at given position\n",idx);
return;
}
int mx=0,my=0;
int sgn=dx<0?-1:1;
while(mx!=dx){
queue<int> q;
vector<bool> was(windows.size(),false);
was[j]=true;
q.push(j);
while(q.size()){
int u=q.front();
q.pop();
for(int v=0;v<windows.size();v++){
if(!was[v] && windows[u].CheckX(windows[v],sgn)){
was[v]=true;
q.push(v);
}
}
}
int mxmv=W;
for(int i=0;i<windows.size();i++){
if(was[i]){
if(sgn==1)mxmv=min(mxmv,W-windows[i].x-windows[i].w);
if(sgn==-1)mxmv=min(mxmv,windows[i].x);
}
}
if(mxmv==0)break;
for(int i=0;i<windows.size();i++){
if(was[i]){
for(int j=0;j<windows.size();j++){
if(!was[j]){
if(windows[i].OverlapY(windows[j])){
if(sgn==1){
if(windows[j].x>windows[i].x){
mxmv=min(mxmv,windows[j].x-windows[i].x-windows[i].w);
}
}else{
if(windows[j].x<windows[i].x){
mxmv=min(mxmv,windows[i].x-windows[j].x-windows[j].w);
}
}
}
}
}
}
}
mxmv=min(mxmv,abs(dx)-abs(mx));
for(int i=0;i<windows.size();i++){
if(was[i])windows[i].x+=sgn*mxmv;
}
mx+=sgn*mxmv;
}
sgn=dy<0?-1:1;
while(my!=dy){
queue<int> q;
vector<bool> was(windows.size(),false);
was[j]=true;
q.push(j);
while(q.size()){
int u=q.front();
q.pop();
for(int v=0;v<windows.size();v++){
if(!was[v] && windows[u].CheckY(windows[v],sgn)){
was[v]=true;
q.push(v);
}
}
}
int mxmv=H;
for(int i=0;i<windows.size();i++){
if(was[i]){
if(sgn==1)mxmv=min(mxmv,H-windows[i].y-windows[i].h);
if(sgn==-1)mxmv=min(mxmv,windows[i].y);
}
}
if(mxmv==0)break;
for(int i=0;i<windows.size();i++){
if(was[i]){
for(int j=0;j<windows.size();j++){
if(!was[j]){
if(windows[i].OverlapX(windows[j])){
if(sgn==1){
if(windows[j].y>windows[i].y){
mxmv=min(mxmv,windows[j].y-windows[i].y-windows[i].h);
}
}else{
if(windows[j].y<windows[i].y){
mxmv=min(mxmv,windows[i].y-windows[j].y-windows[j].h);
}
}
}
}
}
}
}
mxmv=min(mxmv,abs(dy)-abs(my));
for(int i=0;i<windows.size();i++){
if(was[i])windows[i].y+=sgn*mxmv;
}
my+=sgn*mxmv;
}
if(mx!=dx)printf("Command %i: MOVE - moved %i instead of %i\n",idx,abs(mx),abs(dx));
if(my!=dy)printf("Command %i: MOVE - moved %i instead of %i\n",idx,abs(my),abs(dy));
}
int main(){
scanf("%i %i",&W,&H);
int idx=0;
while(scanf("%s",cmd)==1){
idx++;
if(cmd[0]=='O'){
int x,y,w,h;
scanf("%i %i %i %i",&x,&y,&w,&h);
Add(Window(x,y,w,h),idx);
}else if(cmd[0]=='R'){
int x,y,w,h;
scanf("%i %i %i %i",&x,&y,&w,&h);
Resize(x,y,w,h,idx);
}else if(cmd[0]=='C'){
int x,y;
scanf("%i %i",&x,&y);
Close(x,y,idx);
}else if(cmd[0]=='M'){
int x,y,dx,dy;
scanf("%i %i %i %i",&x,&y,&dx,&dy);
Move(x,y,dx,dy,idx);
}
}
printf("%i window(s):\n",windows.size());
for(int i=0;i<windows.size();i++){
printf("%i %i %i %i\n",windows[i].x,windows[i].y,windows[i].w,windows[i].h);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3804kb
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: 3788kb
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: -100
Wrong Answer
time: 1ms
memory: 3808kb
input:
10 10 OPEN 2 2 8 8 MOVE 3 3 -5 0
output:
Command 1: OPEN - window does not fit Command 2: MOVE - no window at given position 0 window(s):
result:
wrong answer 1st lines differ - expected: 'Command 2: MOVE - moved 2 instead of 5', found: 'Command 1: OPEN - window does not fit'