Submission #446254

#	Time	Username	Problem	Language	Result	Execution time	Memory
446254		Haruto810198	Scissors and Tape (CEOI19_scissors)	C++17	30 / 100	1100 ms	207692 KiB

scissors

#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);

    ret.pt[1] = mkp(_x + _dy, _y);
    ret.pt[2] = mkp(_x + _dy, _y + _dx);
    ret.pt[3] = mkp(_x, _y + _dx);

    FOR(i, 0, 3, 1){
        SS.pt[i] = ret.pt[(i+1)%4];
    }

    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 == 3);
    //assert(_pt[2].S == 8);
    //

    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;
    }

    //
    //assert(_pt[2].F == 4);
    //assert(_pt[2].S == 6);
    //

    Shape TT(-1, _pt);

    /// solve
    solve(SS, TT);

    /// tape
    tape(qu, TT);

    return 0;

}

• Subtask 1: 5 / 5
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 10
• Subtask 6: 0 / 16
• Subtask 7: 0 / 11
• Subtask 8: 0 / 19