Submission #267230

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

towerdefense

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

int32_t main(){
    int x0, y0, x1, y1, d; cin >> x0 >> y0 >> x1 >> y1 >> d;
    if(x0 > x1){
        swap(x0, x1);
        swap(y0, y1);
    }
    int d1 = abs(y1-y0) + x1-x0;
    if((d1 > d) || ((d1^d) & 1) || (d1 == 1 && d > 1) || ((x1-x0) == 1 && abs(y1-y0) == 1 && d == 4)){
        cout << "impossible" << endl;
        exit(0);
    }
    if(d == d1){
        cout << 0 << endl;
        exit(0);
    }
    //a solution exists, start has lower x
    //cases: diff x >= 2, vertical line of turrets
    //diff y >= 2
    //x0+1, y0+-1
    if(x1 > 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){
        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