Submission #1128915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128915		nhanhoang510	Tiles (BOI24_tiles)	C++20	4 / 100	38 ms	4168 KiB

Main

#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int maxn = 2 * 1e5 + 7;
const int LOG = 20;
const long long MOD = (long long)(1e9) + 7;
const long long base = 311;
const int ALP_BET = 26;

typedef pair<int, int> ii;
typedef pair<int, long long> il;
typedef pair<long long, int> li;
typedef pair<long long, long long> ll;

const int INF = (int)(1e9) + 7;

struct Point{
    int x, y;
};

int n, m;
Point pts[maxn];

int getres(int a, int b){
    if(b % 2 != 0)
        return 0;
    return (a / 2) * 2;
}

namespace SUB1{

void solve(){
    int maxx = 0, miny = INF, maxy = 0;
    for(int i = 1; i <= n; ++i){
        maxx = max(maxx, pts[i].x);
        miny = min(miny, pts[i].y);
        maxy = max(maxy, pts[i].y);
    }
    int ans = getres(maxx, maxy - miny);
    cout << ans << "\n";
    return;
}

}

namespace SUB2{

Point save[maxn];

bool check_near(Point a, Point b){
    return (a.x == b.x || a.y == b.y);
}

void clean(){
    int pos = 1;
    for(int i = 1; i <= n; ++i) if(pts[i].x == 0){
        pos = i;
        break;
    }
    int nn = 0;
    for(int i = pos; i <= n; ++i){
        ++nn;
        save[nn] = pts[i];
    }
    for(int i = 1; i < pos; ++i){
        ++nn;
        save[nn] = pts[i];
    }
    for(int i = 1; i <= n; ++i) pts[i] = save[i];
    pts[n + 1] = pts[1];
    nn = 1; save[1] = pts[1];
    for(int i = 2; i <= n; ++i){
        if(!check_near(save[nn], pts[i + 1])){
            ++nn;
            save[nn] = pts[i];
        }
    }
    n = nn;
    for(int i = 1; i <= n; ++i)
        pts[i] = save[i];
    return;
}

void clean_vector(vector<int> &x){
    sort(x.begin(), x.end());
    x.resize(unique(x.begin(), x.end()) - x.begin());
    return;
}

void solve(){
    clean();
    if(n == 4){
        SUB1::solve();
        return;
    }
    int up = 0, down = INF, h, miny = INF, maxy = 0;
    vector<int> xx;
    for(int i = 1; i <= n; ++i){
        if(pts[i].x == 0){
            up = max(up, pts[i].y);
            down = min(down, pts[i].y);
        }
        xx.push_back(pts[i].x);
    }
    clean_vector(xx);
    for(int i = 1; i <= n; ++i) if(pts[i].x == xx[2]){
        miny = min(miny, pts[i].y);
        maxy = max(maxy, pts[i].y);
    }
    h = maxy - miny;

    int ans = 111;
    if((up - down) % 2 == 0){
        ans = getres(xx[1] - xx[0], up - down) + getres(xx[2] - xx[1], h);
    }else
        ans = getres(xx[1] - xx[0], up - down);
    cout << ans << "\n";
    return;
}

}

namespace SUB3{

int nn;
Point arr[maxn];

void solve(){
    SUB2::clean();
    nn = 0;
    for(int i = 1; i <= n - 2; i = i + 2){
        ++nn; arr[nn] = {pts[i + 1].x - pts[i].x, pts[i].y};
    }
    int ans = 0;
    for(int i = 1; i <= nn; ++i) if(arr[i].y % 2 != 0){
        break;
    } else{
        ans = ans + getres(arr[i].x, arr[i].y);
        if(arr[i].x % 2 != 0)
            break;
    }
    cout << ans << "\n";
    return;
}

}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    // freopen("Tiles.INP","r",stdin);
    // freopen("Tiles.OUT","w",stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> pts[i].x >> pts[i].y;
    }
    if(n == 4){
        SUB1::solve();
    } else
    if(n <= 6){
        SUB2::solve();
    } else
        SUB3::solve();
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 9
• Subtask 3: 0 / 11
• Subtask 4: 0 / 19
• Subtask 5: 0 / 22
• Subtask 6: 0 / 25
• Subtask 7: 0 / 10