oj.uz

Submission #446254

# Submission time Handle Problem Language Result Execution time Memory
446254 2021-07-21T11:03:30 Z Haruto810198 Scissors and Tape (CEOI19_scissors) C++17
30 / 100
 1000 ms 207692 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB used 64 vertices, largest error was 0.00000000850000
2 Correct 1 ms 204 KB used 36 vertices, largest error was 0.00000000800000
3 Correct 1 ms 316 KB used 76 vertices, largest error was 0.00000000866667
4 Correct 0 ms 204 KB used 36 vertices, largest error was 0.00000000800000
5 Correct 0 ms 204 KB used 44 vertices, largest error was 0.00000000800000
6 Correct 0 ms 204 KB used 36 vertices, largest error was 0.00000000800000
7 Correct 1 ms 204 KB used 44 vertices, largest error was 0.00000000800000
8 Correct 1 ms 204 KB used 76 vertices, largest error was 0.00000000880000
9 Correct 1 ms 204 KB used 84 vertices, largest error was 0.00000000880000
10 Correct 0 ms 204 KB used 36 vertices, largest error was 0.00000000800000

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB used 172 vertices, largest error was 0.00000000800000
2 Correct 1 ms 204 KB used 76 vertices, largest error was 0.00000000800000
3 Correct 1 ms 204 KB used 216 vertices, largest error was 0.00000004000000
4 Correct 1 ms 332 KB used 704 vertices, largest error was 0.00000003999902
5 Correct 1 ms 204 KB used 224 vertices, largest error was 0.00000002600000
6 Correct 1 ms 204 KB used 224 vertices, largest error was 0.00000003963578
7 Correct 1 ms 204 KB used 184 vertices, largest error was 0.00000000900000
8 Correct 1 ms 332 KB used 1032 vertices, largest error was 0.00000002500000
9 Correct 0 ms 204 KB used 84 vertices, largest error was 0.00000004000000
10 Correct 1 ms 332 KB used 312 vertices, largest error was 0.00000000900000

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB used 64 vertices, largest error was 0.00000000850000
2 Correct 1 ms 204 KB used 36 vertices, largest error was 0.00000000800000
3 Correct 1 ms 316 KB used 76 vertices, largest error was 0.00000000866667
4 Correct 0 ms 204 KB used 36 vertices, largest error was 0.00000000800000
5 Correct 0 ms 204 KB used 44 vertices, largest error was 0.00000000800000
6 Correct 0 ms 204 KB used 36 vertices, largest error was 0.00000000800000
7 Correct 1 ms 204 KB used 44 vertices, largest error was 0.00000000800000
8 Correct 1 ms 204 KB used 76 vertices, largest error was 0.00000000880000
9 Correct 1 ms 204 KB used 84 vertices, largest error was 0.00000000880000
10 Correct 0 ms 204 KB used 36 vertices, largest error was 0.00000000800000
11 Correct 0 ms 204 KB used 172 vertices, largest error was 0.00000000800000
12 Correct 1 ms 204 KB used 76 vertices, largest error was 0.00000000800000
13 Correct 1 ms 204 KB used 216 vertices, largest error was 0.00000004000000
14 Correct 1 ms 332 KB used 704 vertices, largest error was 0.00000003999902
15 Correct 1 ms 204 KB used 224 vertices, largest error was 0.00000002600000
16 Correct 1 ms 204 KB used 224 vertices, largest error was 0.00000003963578
17 Correct 1 ms 204 KB used 184 vertices, largest error was 0.00000000900000
18 Correct 1 ms 332 KB used 1032 vertices, largest error was 0.00000002500000
19 Correct 0 ms 204 KB used 84 vertices, largest error was 0.00000004000000
20 Correct 1 ms 332 KB used 312 vertices, largest error was 0.00000000900000
21 Correct 1 ms 204 KB used 332 vertices, largest error was 0.00000002500000
22 Correct 1 ms 204 KB used 284 vertices, largest error was 0.00000002500000
23 Correct 1 ms 332 KB used 404 vertices, largest error was 0.00000002500000
24 Correct 1 ms 332 KB used 532 vertices, largest error was 0.00000002500000
25 Correct 1 ms 204 KB used 232 vertices, largest error was 0.00000000800000
26 Correct 1 ms 204 KB used 236 vertices, largest error was 0.00000002400000
27 Correct 1 ms 332 KB used 472 vertices, largest error was 0.00000002400000
28 Correct 1 ms 332 KB used 556 vertices, largest error was 0.00000002593041
29 Correct 1 ms 312 KB used 312 vertices, largest error was 0.00000002400000
30 Correct 1 ms 204 KB used 184 vertices, largest error was 0.00000004000000

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1100 ms 207692 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB used 64 vertices, largest error was 0.00000000850000
2 Correct 1 ms 204 KB used 36 vertices, largest error was 0.00000000800000
3 Correct 1 ms 316 KB used 76 vertices, largest error was 0.00000000866667
4 Correct 0 ms 204 KB used 36 vertices, largest error was 0.00000000800000
5 Correct 0 ms 204 KB used 44 vertices, largest error was 0.00000000800000
6 Correct 0 ms 204 KB used 36 vertices, largest error was 0.00000000800000
7 Correct 1 ms 204 KB used 44 vertices, largest error was 0.00000000800000
8 Correct 1 ms 204 KB used 76 vertices, largest error was 0.00000000880000
9 Correct 1 ms 204 KB used 84 vertices, largest error was 0.00000000880000
10 Correct 0 ms 204 KB used 36 vertices, largest error was 0.00000000800000
11 Correct 0 ms 204 KB used 172 vertices, largest error was 0.00000000800000
12 Correct 1 ms 204 KB used 76 vertices, largest error was 0.00000000800000
13 Correct 1 ms 204 KB used 216 vertices, largest error was 0.00000004000000
14 Correct 1 ms 332 KB used 704 vertices, largest error was 0.00000003999902
15 Correct 1 ms 204 KB used 224 vertices, largest error was 0.00000002600000
16 Correct 1 ms 204 KB used 224 vertices, largest error was 0.00000003963578
17 Correct 1 ms 204 KB used 184 vertices, largest error was 0.00000000900000
18 Correct 1 ms 332 KB used 1032 vertices, largest error was 0.00000002500000
19 Correct 0 ms 204 KB used 84 vertices, largest error was 0.00000004000000
20 Correct 1 ms 332 KB used 312 vertices, largest error was 0.00000000900000
21 Correct 1 ms 204 KB used 332 vertices, largest error was 0.00000002500000
22 Correct 1 ms 204 KB used 284 vertices, largest error was 0.00000002500000
23 Correct 1 ms 332 KB used 404 vertices, largest error was 0.00000002500000
24 Correct 1 ms 332 KB used 532 vertices, largest error was 0.00000002500000
25 Correct 1 ms 204 KB used 232 vertices, largest error was 0.00000000800000
26 Correct 1 ms 204 KB used 236 vertices, largest error was 0.00000002400000
27 Correct 1 ms 332 KB used 472 vertices, largest error was 0.00000002400000
28 Correct 1 ms 332 KB used 556 vertices, largest error was 0.00000002593041
29 Correct 1 ms 312 KB used 312 vertices, largest error was 0.00000002400000
30 Correct 1 ms 204 KB used 184 vertices, largest error was 0.00000004000000
31 Runtime error 1 ms 460 KB Execution killed with signal 6
32 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB used 64 vertices, largest error was 0.00000000850000
2 Correct 1 ms 204 KB used 36 vertices, largest error was 0.00000000800000
3 Correct 1 ms 316 KB used 76 vertices, largest error was 0.00000000866667
4 Correct 0 ms 204 KB used 36 vertices, largest error was 0.00000000800000
5 Correct 0 ms 204 KB used 44 vertices, largest error was 0.00000000800000
6 Correct 0 ms 204 KB used 36 vertices, largest error was 0.00000000800000
7 Correct 1 ms 204 KB used 44 vertices, largest error was 0.00000000800000
8 Correct 1 ms 204 KB used 76 vertices, largest error was 0.00000000880000
9 Correct 1 ms 204 KB used 84 vertices, largest error was 0.00000000880000
10 Correct 0 ms 204 KB used 36 vertices, largest error was 0.00000000800000
11 Correct 0 ms 204 KB used 172 vertices, largest error was 0.00000000800000
12 Correct 1 ms 204 KB used 76 vertices, largest error was 0.00000000800000
13 Correct 1 ms 204 KB used 216 vertices, largest error was 0.00000004000000
14 Correct 1 ms 332 KB used 704 vertices, largest error was 0.00000003999902
15 Correct 1 ms 204 KB used 224 vertices, largest error was 0.00000002600000
16 Correct 1 ms 204 KB used 224 vertices, largest error was 0.00000003963578
17 Correct 1 ms 204 KB used 184 vertices, largest error was 0.00000000900000
18 Correct 1 ms 332 KB used 1032 vertices, largest error was 0.00000002500000
19 Correct 0 ms 204 KB used 84 vertices, largest error was 0.00000004000000
20 Correct 1 ms 332 KB used 312 vertices, largest error was 0.00000000900000
21 Correct 1 ms 204 KB used 332 vertices, largest error was 0.00000002500000
22 Correct 1 ms 204 KB used 284 vertices, largest error was 0.00000002500000
23 Correct 1 ms 332 KB used 404 vertices, largest error was 0.00000002500000
24 Correct 1 ms 332 KB used 532 vertices, largest error was 0.00000002500000
25 Correct 1 ms 204 KB used 232 vertices, largest error was 0.00000000800000
26 Correct 1 ms 204 KB used 236 vertices, largest error was 0.00000002400000
27 Correct 1 ms 332 KB used 472 vertices, largest error was 0.00000002400000
28 Correct 1 ms 332 KB used 556 vertices, largest error was 0.00000002593041
29 Correct 1 ms 312 KB used 312 vertices, largest error was 0.00000002400000
30 Correct 1 ms 204 KB used 184 vertices, largest error was 0.00000004000000
31 Runtime error 1 ms 460 KB Execution killed with signal 6
32 Halted 0 ms 0 KB -

Subtask #8
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB used 64 vertices, largest error was 0.00000000850000
2 Correct 1 ms 204 KB used 36 vertices, largest error was 0.00000000800000
3 Correct 1 ms 316 KB used 76 vertices, largest error was 0.00000000866667
4 Correct 0 ms 204 KB used 36 vertices, largest error was 0.00000000800000
5 Correct 0 ms 204 KB used 44 vertices, largest error was 0.00000000800000
6 Correct 0 ms 204 KB used 36 vertices, largest error was 0.00000000800000
7 Correct 1 ms 204 KB used 44 vertices, largest error was 0.00000000800000
8 Correct 1 ms 204 KB used 76 vertices, largest error was 0.00000000880000
9 Correct 1 ms 204 KB used 84 vertices, largest error was 0.00000000880000
10 Correct 0 ms 204 KB used 36 vertices, largest error was 0.00000000800000
11 Correct 0 ms 204 KB used 172 vertices, largest error was 0.00000000800000
12 Correct 1 ms 204 KB used 76 vertices, largest error was 0.00000000800000
13 Correct 1 ms 204 KB used 216 vertices, largest error was 0.00000004000000
14 Correct 1 ms 332 KB used 704 vertices, largest error was 0.00000003999902
15 Correct 1 ms 204 KB used 224 vertices, largest error was 0.00000002600000
16 Correct 1 ms 204 KB used 224 vertices, largest error was 0.00000003963578
17 Correct 1 ms 204 KB used 184 vertices, largest error was 0.00000000900000
18 Correct 1 ms 332 KB used 1032 vertices, largest error was 0.00000002500000
19 Correct 0 ms 204 KB used 84 vertices, largest error was 0.00000004000000
20 Correct 1 ms 332 KB used 312 vertices, largest error was 0.00000000900000
21 Correct 1 ms 204 KB used 332 vertices, largest error was 0.00000002500000
22 Correct 1 ms 204 KB used 284 vertices, largest error was 0.00000002500000
23 Correct 1 ms 332 KB used 404 vertices, largest error was 0.00000002500000
24 Correct 1 ms 332 KB used 532 vertices, largest error was 0.00000002500000
25 Correct 1 ms 204 KB used 232 vertices, largest error was 0.00000000800000
26 Correct 1 ms 204 KB used 236 vertices, largest error was 0.00000002400000
27 Correct 1 ms 332 KB used 472 vertices, largest error was 0.00000002400000
28 Correct 1 ms 332 KB used 556 vertices, largest error was 0.00000002593041
29 Correct 1 ms 312 KB used 312 vertices, largest error was 0.00000002400000
30 Correct 1 ms 204 KB used 184 vertices, largest error was 0.00000004000000
31 Runtime error 1 ms 460 KB Execution killed with signal 6
32 Halted 0 ms 0 KB -