Submission #446239

#TimeUsernameProblemLanguageResultExecution timeMemory
446239Haruto810198Scissors and Tape (CEOI19_scissors)C++17
0 / 100
1 ms460 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define double long double #define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d)) #define szof(x) ((int)(x).size()) #define vi vector<int> #define pii pair<int,int> #define F first #define S second #define pb push_back #define eb emplace_back #define mkp make_pair const int INF = 2147483647; const int LNF = INF*INF; const int MOD = 1000000007; const int mod = 998244353; const double eps = 1e-12; //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") struct Shape{ int ID; vector<pii> pt; Shape(int _ID, vector<pii> _pt) : ID(_ID), pt(_pt) {} }; int IDs; vector<Shape> qu; inline int dx(Shape SS){ return (SS.pt[1].F - SS.pt[0].F); } inline int dy(Shape SS){ return (SS.pt[2].S - SS.pt[1].S); } void scissors(Shape from, vector<Shape> to){ cout<<"scissors"<<'\n'; cout<<from.ID<<" "<<szof(to)<<'\n'; for(Shape SS : to){ cout<<szof(SS.pt)<<" "; for(pii p : SS.pt){ cout<<p.F<<" "<<p.S<<" "; } cout<<'\n'; } } void tape(vector<Shape> from, Shape to){ cout<<"tape"<<'\n'; cout<<szof(from)<<" "; for(Shape SS : from){ cout<<SS.ID<<" "; } cout<<'\n'; for(Shape SS : from){ cout<<szof(SS.pt)<<" "; for(pii p : SS.pt){ cout<<p.F<<" "<<p.S<<" "; } cout<<'\n'; } cout<<szof(to.pt)<<" "; for(pii p : to.pt){ cout<<p.F<<" "<<p.S<<" "; } cout<<'\n'; } Shape Flip(Shape SS){ Shape ret = SS; ret.ID = IDs; IDs++; int _x = SS.pt[0].F; int _y = SS.pt[0].S; int _dx = dx(SS); int _dy = dy(SS); SS.pt[1] = mkp(_x + _dy, _y); SS.pt[2] = mkp(_x + _dy, _y + _dx); SS.pt[3] = mkp(_x, _y + _dx); ret.pt[1] = mkp(_x + _dy, _y); ret.pt[2] = mkp(_x + _dy, _y + _dx); ret.pt[3] = mkp(_x, _y + _dx); tape({SS}, ret); return ret; } Shape Move(Shape SS, int move_x, int move_y){ Shape ret = SS; ret.ID = IDs; IDs++; for(pii& p : SS.pt){ p.F += move_x; p.S += move_y; } for(pii& p : ret.pt){ p.F += move_x; p.S += move_y; } tape({SS}, ret); return ret; } vector<Shape> Cut_x(Shape from, int cut_sz){ Shape S0 = from; Shape S1 = from; int _x = from.pt[0].F; S0.ID = IDs; IDs++; S0.pt[1].F = _x + cut_sz; S0.pt[2].F = _x + cut_sz; S1.ID = IDs; IDs++; S1.pt[0].F = _x + cut_sz; S1.pt[3].F = _x + cut_sz; scissors(from, {S0, S1}); return {S0, S1}; } vector<Shape> Cut_y(Shape from, int cut_sz){ Shape S0 = from; Shape S1 = from; int _y = from.pt[0].S; S0.ID = IDs; IDs++; S0.pt[2].S = _y + cut_sz; S0.pt[3].S = _y + cut_sz; S1.ID = IDs; IDs++; S1.pt[0].S = _y + cut_sz; S1.pt[1].S = _y + cut_sz; scissors(from, {S0, S1}); return {S0, S1}; } void solve(Shape SS, Shape TT){ /* cerr<<endl; cerr<<"solve "<<endl; for(pii p : SS.pt){ cerr<<p.F<<" "<<p.S<<" "; } cerr<<endl; for(pii p : TT.pt){ cerr<<p.F<<" "<<p.S<<" "; } cerr<<endl; cerr<<endl; */ /// end of recursion if(dx(SS) == dx(TT) and dy(SS) == dy(TT)){ qu.pb(SS); return; } /// flip SS if necessary int area0 = min(dx(SS), dx(TT)) * min(dy(SS), dy(TT)); int area1 = min(dy(SS), dx(TT)) * min(dx(SS), dy(TT)); if(area0 < area1){ SS = Flip(SS); } /// cut SS and update TT vector<Shape> Cut; if(dx(SS) > dx(TT)){ Cut = Cut_x(SS, dx(TT)); qu.pb(Cut[0]); TT.pt[0].S += dy(SS); TT.pt[1].S += dy(SS); } else if(dx){ Cut = Cut_y(SS, dy(TT)); qu.pb(Cut[0]); TT.pt[0].F += dx(SS); TT.pt[3].F += dx(SS); } /// move Cut[1] to TT int move_x = TT.pt[0].F - Cut[1].pt[0].F; int move_y = TT.pt[0].S - Cut[1].pt[0].S; Cut[1] = Move(Cut[1], move_x, move_y); /// recurse solve(Cut[1], TT); } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int sz; vector<pii> _pt; /// input SS cin>>sz; _pt.resize(sz); FOR(i, 0, sz-1, 1){ cin>>_pt[i].F>>_pt[i].S; } // assert(_pt[2].F == 10); // Shape SS(0, _pt); IDs = 1; /// input TT cin>>sz; _pt.resize(sz); FOR(i, 0, sz-1, 1){ cin>>_pt[i].F>>_pt[i].S; } Shape TT(-1, _pt); /// solve solve(SS, TT); /// tape tape(qu, TT); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...