QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #557034 | #4688. Window Manager | AllSolvedin1557 | WA | 1ms | 3880kb | C++17 | 7.8kb | 2024-09-11 00:26:34 | 2024-09-11 00:26:35 |
Judging History
answer
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef long double ld;
struct dat{
ll x,y,w,h,time;
bool inc(ll a,ll b) { return (x<=a&&a<=x+w&&y<=b&&b<=y+h); }
bool myinc(ll a,ll b) { return (x<=a&&a<x+w&&y<=b&&b<y+h); }
bool in(ll a,ll b) { return (x<a&&a<x+w&&y<b&&b<y+h); }
bool inter(dat d) { return d.in(x,y)||d.in(x,y+h)||d.in(x+w,y)||d.in(x+w,y+h); }
bool inc(dat d) { return inc(d.x,d.y)&&inc(d.x,d.y+d.h)&&inc(d.x+d.w,d.y)&&inc(d.x+d.w,d.y+d.h); }
bool interx(dat d) { return (y<d.y+d.h&&d.y<y+h); }
bool intery(dat d) { return (x<d.x+d.w&&d.x<x+w); }
bool operator==(const dat &d)
{
return x==d.x&&y==d.y&&h==d.h&&w==d.w;
}
};
vector<dat>W;
void notfit(ll cnt, string &comm)
{ cout<<"Command "<<cnt<<": "<<comm<<" - window does not fit\n"; }
void notpos(ll cnt, string &comm)
{ cout<<"Command "<<cnt<<": "<<comm<<" - no window at given position\n"; }
void notmov(ll cnt, string &comm, ll real, ll fact)
{ cout<<"Command "<<cnt<<": "<<comm<<" - moved "<<real<<" instead of "<<fact<<"\n"; }
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
ll X,Y,cnt=0; cin>>X>>Y;
bool debug = 0;
dat S={0,0,X,Y};
while(1)
{
string s;
cin>>s;
cnt++;
if(debug)
{
cout<<cnt<<'\n';
cout<<"-------\n";
for(auto [x,y,w,h,t]:W) cout<<x<<' '<<y<<' '<<w<<' '<<h<<' '<<t<<'\n';
cout<<"-------\n";
}
if(cin.eof()) break;
if(s=="OPEN")
{
ll x,y,w,h; cin>>x>>y>>w>>h;
dat now={x,y,w,h,cnt};
if(!S.inc(now))
{
notfit(cnt,s);
continue;
}
bool flag=1;
for(auto d:W)
if(d.inter(now)) flag=0;
if(flag)
W.push_back(now);
else notfit(cnt,s);
}
if(s=="RESIZE")
{
ll x,y,w,h; cin>>x>>y>>w>>h;
ll ex=-1;
for(int i=0;i<W.size();i++) if(W[i].myinc(x,y)) ex=i;
if(ex==-1)
{
notpos(cnt,s);
continue;
}
dat prv=W[ex];
W.erase(W.begin()+ex);
dat now=prv; now.w=w; now.h=h;
if(!S.inc(now))
{
W.push_back(prv);
notfit(cnt,s);
continue;
}
bool flag=1;
for(auto d:W)
if(d.inter(now)) flag=0;
if(flag)
W.push_back(now);
else W.push_back(prv), notfit(cnt,s);
}
if(s=="CLOSE")
{
ll x,y; cin>>x>>y;
ll ex=-1;
for(int i=0;i<W.size();i++) if(W[i].myinc(x,y)) ex=i;
if(ex==-1)
{
notpos(cnt,s);
continue;
}
W.erase(W.begin()+ex);
}
if(s=="MOVE")
{
ll x,y,dx,dy; cin>>x>>y>>dx>>dy;
ll ex=-1;
for(int i=0;i<W.size();i++) if(W[i].myinc(x,y)) ex=i;
if(ex==-1)
{
notpos(cnt,s);
continue;
}
dat now=W[ex];
if(dx>0)
{
sort(W.begin(),W.end(),[](dat a,dat b){ return a.x<b.x; });
int pos;
for(int i=0;i<W.size();i++) if(W[i]==now) pos=i;
vector<ll>dist(W.size(),0);
ll over=0;
for(ll i=pos;i<W.size();i++)
{
if(i==pos) dist[i]=dx;
else
{
for(ll j=pos;j<i;j++)
{
if(W[i].interx(W[j]))
dist[i]=max(dist[i],dist[j]-abs(W[i].x-W[j].x-W[j].w));
}
}
over=max(over,dist[i]-(X-W[i].x-W[i].w));
}
if(over>0) notmov(cnt,s,dx-over,dx);
for(ll i=pos;i<W.size();i++)
{
W[i].x+=max(0LL,dist[i]-over);
}
}
if(dx<0)
{
sort(W.begin(),W.end(),[](dat a,dat b){ return a.x>b.x; });
dx*=-1;
int pos;
for(int i=0;i<W.size();i++) if(W[i]==now) pos=i;
vector<ll>dist(W.size(),0);
ll over=0;
for(ll i=pos;i<W.size();i++)
{
if(i==pos) dist[i]=dx;
else
{
for(ll j=pos;j<i;j++)
{
if(W[i].interx(W[j]))
dist[i]=max(dist[i],dist[j]-abs(W[i].x-W[j].x+W[i].w));
}
}
over=max(over,dist[i]-(W[i].x));
}
if(over>0) notmov(cnt,s,dx-over,dx);
for(ll i=pos;i<W.size();i++)
{
W[i].x-=max(0LL,dist[i]-over);
}
}
if(dy>0)
{
sort(W.begin(),W.end(),[](dat a,dat b){ return a.y<b.y; });
int pos;
for(int i=0;i<W.size();i++) if(W[i]==now) pos=i;
vector<ll>dist(W.size(),0);
ll over=0;
for(ll i=pos;i<W.size();i++)
{
if(i==pos) dist[i]=dy;
else
{
for(ll j=pos;j<i;j++)
{
if(W[i].intery(W[j]))
dist[i]=max(dist[i],dist[j]-abs(W[i].y-W[j].y-W[j].h));
}
}
over=max(over,dist[i]-(Y-W[i].y-W[i].h));
}
if(over>0) notmov(cnt,s,dy-over,dy);
for(ll i=pos;i<W.size();i++)
{
W[i].y+=max(0LL,dist[i]-over);
}
}
if(dy<0)
{
sort(W.begin(),W.end(),[](dat a,dat b){ return a.y>b.y; });
dy*=-1;
int pos;
for(int i=0;i<W.size();i++) if(W[i]==now) pos=i;
if(debug)
{
cout<<cnt<<'\n';
cout<<"-------\n";
for(auto [x,y,w,h,t]:W) cout<<x<<' '<<y<<' '<<w<<' '<<h<<' '<<t<<'\n';
cout<<"-------\n";
}
vector<ll>dist(W.size(),0);
ll over=0;
for(ll i=pos;i<W.size();i++)
{
if(i==pos) dist[i]=dy;
else
{
for(ll j=pos;j<i;j++)
{
if(W[i].intery(W[j]))
dist[i]=max(dist[i],dist[j]-abs(W[i].y-W[j].y+W[i].h));
}
}
over=max(over,dist[i]-(W[i].y));
}
if(over>0) notmov(cnt,s,dy-over,dy);
for(ll i=pos;i<W.size();i++)
{
W[i].y-=max(0LL,dist[i]-over);
}
}
}
}
sort(W.begin(),W.end(),[](dat a,dat b){ return a.time<b.time; });
cout<<W.size()<<" window(s):\n";
for(auto [x,y,w,h,t]:W) cout<<x<<' '<<y<<' '<<w<<' '<<h<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3836kb
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: 0ms
memory: 3636kb
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: 0ms
memory: 3608kb
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: 0ms
memory: 3580kb
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: 3632kb
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: 3596kb
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: 0ms
memory: 3636kb
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: 3516kb
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: 0ms
memory: 3876kb
input:
320 200
output:
0 window(s):
result:
ok single line: '0 window(s):'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3584kb
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 1047976 524288 100 524288 1048076 0 100 262144 1048076 262144 100 262144 1048076 524288 100 262144 1048076 786432 100 262144 1048176 0 100 131072 1048176 131072 100 131072 1048176 262144 10...
result:
ok 129 lines
Test #11:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
1000 1000 OPEN 0 0 1 1 MOVE 0 0 100000 0 MOVE 999 0 0 100000 MOVE 999 999 -100000 0 MOVE 0 999 0 -100000
output:
Command 2: MOVE - moved 999 instead of 100000 Command 3: MOVE - moved 999 instead of 100000 Command 4: MOVE - moved 999 instead of 100000 Command 5: MOVE - moved 999 instead of 100000 1 window(s): 0 0 1 1
result:
ok 6 lines
Test #12:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
1000000000 1000000000 OPEN 843863694 500000001 20 20 OPEN 766187149 500000004 20 20 OPEN 13035129 500000000 20 20 OPEN 798317341 499999996 20 20 OPEN 483704743 500000004 20 20 OPEN 922731855 500000003 20 20 OPEN 931133659 500000001 20 20 OPEN 160148701 499999995 20 20 OPEN 343043291 499999995 20 20 ...
output:
Command 101: MOVE - moved 998944099 instead of 1000000000 100 window(s): 999999640 500000001 20 20 999999560 500000004 20 20 999998100 500000000 20 20 999999580 499999996 20 20 999999060 500000004 20 20 999999840 500000003 20 20 999999860 500000001 20 20 999998500 499999995 20 20 999998860 499999995...
result:
ok 102 lines
Test #13:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
1000000000 1000000000 OPEN 8095 50000030 1000 1000 OPEN 56873 355000042 1000 1000 OPEN 14421 90000036 1000 1000 OPEN 16813 105000063 1000 1000 OPEN 1625 10000002 1000 1000 OPEN 19287 120000007 1000 1000 OPEN 64021 400000022 1000 1000 OPEN 79236 495000076 1000 1000 OPEN 73600 460000092 1000 1000 OPEN...
output:
Command 101: MOVE - moved 999899990 instead of 1000000000 100 window(s): 8095 899971001 1000 1000 56873 999971000 1000 1000 14421 899979001 1000 1000 16813 899982001 1000 1000 1625 899963001 1000 1000 19287 899985001 1000 1000 64021 999980000 1000 1000 29236 899999001 1000 1000 73600 999992000 1000 ...
result:
ok 102 lines
Test #14:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
1000 1000 OPEN 0 0 10 10 OPEN 0 999 10 10 OPEN 0 991 10 10 OPEN 0 990 10 10 OPEN 999 0 10 10 OPEN 991 0 10 10 OPEN 990 0 10 10 OPEN 999 999 10 10 OPEN 991 991 10 10 OPEN 990 990 10 10 OPEN 990 500 20 20 OPEN 500 990 20 20 OPEN 10 10 980 980
output:
Command 2: OPEN - window does not fit Command 3: OPEN - window does not fit Command 5: OPEN - window does not fit Command 6: OPEN - window does not fit Command 8: OPEN - window does not fit Command 9: OPEN - window does not fit Command 11: OPEN - window does not fit Command 12: OPEN - window does no...
result:
ok 14 lines
Test #15:
score: -100
Wrong Answer
time: 0ms
memory: 3880kb
input:
1000 500 OPEN 0 0 500 1000 OPEN 0 0 1000 500 OPEN 10 10 10 10
output:
Command 1: OPEN - window does not fit 2 window(s): 0 0 1000 500 10 10 10 10
result:
wrong answer 2nd lines differ - expected: 'Command 3: OPEN - window does not fit', found: '2 window(s):'