Submission #267234

#	Time	Username	Problem	Language	Result	Execution time	Memory
267234		taulant	Tower Defense (CEOI19_towerdefense)	C++14	100 / 100	1 ms	416 KiB

towerdefense

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"

int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int x0, y0, x1, y1, d; cin >> x0 >> y0 >> x1 >> y1 >> d;
    if(x0 > x1){ // 1/2 the cases to handle
        swap(x0, x1);
        swap(y0, y1);
    }
    int d1 = abs(y1-y0) + abs(x1-x0);
    if((d1 > d) || ((d1^d) & 1) || (d1 == 1 && d > 1) || (abs(x1-x0) == 1 && abs(y1-y0) == 1 && d == 4)){
        // d is too short, has different parity, special impossible cases
        cout << "impossible" << endl;
        exit(0);
    }
    if(d == d1){
        cout << 0 << endl;
        exit(0);
    }
    if(x1 > x0+1){
        // make a vertical line at x0+1
        if(y1 < y0) swap(y0, y1);
        int l = (d-d1-2)/2;
        cout << y1-y0+1+l+l << endl;
        for(int i=y0-l; i <= y1+l; ++i) cout << x0+1 << " " << i << endl;
    }
    else if(abs(y1-y0) > 1){
        // make horizontal lines at y0 +- 1
        int l = (d-d1-2)/2;
        cout << 2*(x1-x0+1+l+l) << endl;
        for(int i=x0-l; i <= x1+l; ++i) cout << i << " " << y0+1 << endl;
        for(int i=x0-l; i <= x1+l; ++i) cout << i << " " << y0-1 << endl;
    }
    else if(y1 > y0){ //{x1, y1} = {x0+1, y0+1}
        int l = (d - 4)/2;
        cout << d-4 << endl;
        for(int i=1; i<=l; ++i) cout << x0+i << " " << y0 << endl << x0 << " " << y0+i << endl;
    }
    else { //{x1, y1} = {x0+1, y0-1}
        int l = (d - 4)/2;
        cout << d-4 << endl;
        for(int i=1; i<=l; ++i) cout << x0+i << " " << y0 << endl << x0 << " " << y0-i << endl;
    }
}

• Subtask 1: 25 / 25
• Subtask 2: 28 / 28
• Subtask 3: 47 / 47