Submission #1169563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169563		primenumber_zz	Golf (JOI17_golf)	C++20	30 / 100	342 ms	146848 KiB

golf

#include <string.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template <typename T> using vc = vector<T>;
template <typename T> using vvc = vector<vector<T>>;
template <class S> using pq = priority_queue<S,vector<S>,greater<S>>;
template <class S,class T> inline bool chmax(S &a,const T&b) { return (a < b)?a=b,1:0; }
template <class S,class T> inline bool chmin(S &a,const T&b) { return (a > b)?a=b,1:0; }

#define overlord3(_a,_b,_c,_d,name,...) name
#define REP1(i,n) for(ll i = 0; i < (n); i++) 
#define REP2(i,a,b) for(ll i = (a); i < (b); i++) 
#define REP3(i,a,b,c) for(ll i = (a); i < (b); i += (c))
#define rep(...) overlord3(__VA_ARGS__,REP3,REP2,REP1)(__VA_ARGS__)
#define PER1(i,n) for(ll i = (n)-1; i >= 0; i--)
#define PER2(i,a,b) for(ll i = (a)-1; i >= b; i--)
#define PER3(i,a,b,c) for(ll i = (a)-1; i >= b; i -= c)
#define per(...) overlord3(__VA_ARGS__,PER3,PER2,PER1)(__VA_ARGS__)
#define fi first
#define se second
#define pb push_back
#define si(c) (int)(c).size()
#define all(c) c.begin(),c.end()
#define lb(c,x) distance((c).begin(),lower_bound(all(c),x))
#define ub(c,x) distance((c).begin(),upper_bound(all(c),x))
#define SORT(c) sort(all(c))
#define REV(c) reverse(all(c))
#define UNIQUE(c) SORT(c),c.erase(unique(all(c)),c.end())

int sum[4][2010][2010];
int inf = 1001001001;
int dist[2010][2010][4];
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int S,T,U,V;
    cin >> S >> T >> U >> V;
    int N;
    cin >> N;
    vc<int>A(N),B(N),C(N),D(N),cmp1,cmp2;
    rep(i,N) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
        cmp1.pb(A[i]);
        cmp1.pb(B[i]);
        cmp2.pb(C[i]);
        cmp2.pb(D[i]);
    }
    cmp1.pb(S);
    cmp1.pb(U);
    cmp2.pb(T);
    cmp2.pb(V);
    UNIQUE(cmp1);
    UNIQUE(cmp2);
    assert(N <= 1000);
    rep(i,N) {
        int it1 = lb(cmp1,A[i]);
        int it2 = lb(cmp1,B[i]);
        int it3 = lb(cmp2,C[i]);
        int it4 = lb(cmp2,D[i]);
        sum[0][it1+1][it3]++;
        sum[0][it1+1][it4]--;
        sum[0][it2][it3]--;
        sum[0][it2][it4]++;
        sum[1][it1][it3+1]++;
        sum[1][it1][it4]--;
        sum[1][it2][it3+1]--;
        sum[1][it2][it4]++;
        sum[2][it1+1][it3+1]++;
        sum[2][it1+1][it4+1]--;
        sum[2][it2][it3+1]--;
        sum[2][it2][it4+1]++;
        sum[3][it1+1][it3+1]++;
        sum[3][it1+1][it4]--;
        sum[3][it2+1][it3+1]--;
        sum[3][it2+1][it4]++;
    }
    int W = si(cmp1),H = si(cmp2);
    rep(k,4) {
    rep(i,W) {
        rep(j,H) {
            sum[k][i][j+1] += sum[k][i][j];
        }
    }
    }
    rep(k,4) {
    rep(i,H) {
        rep(j,W) {
            sum[k][j+1][i] += sum[k][j][i];
        }
    }
    }
    rep(i,W) {
        rep(j,H) {
            rep(k,4) {
                dist[i][j][k] = inf;
            }
        }
    }
    int sx = lb(cmp1,S),sy = lb(cmp2,T);
    int gx = lb(cmp1,U),gy = lb(cmp2,V);
    deque<array<int,4>>que;
    rep(i,4) {
        dist[sx][sy][i] = 1;
        que.push_back({1,sx,sy,(int)i});
    }
    while(!que.empty()) {
        auto x = que.front();
        que.pop_front();
        if(dist[x[1]][x[2]][x[3]] != x[0]) continue;
        rep(i,4) {
            int nx = x[1]+dx[i];
            int ny = x[2]+dy[i];
            int nz = i;
            if(nx < 0 || ny < 0 || nx >= W || ny >= H || sum[nz][x[1]][x[2]]) continue;
            if(i == x[3]) {
                if(chmin(dist[nx][ny][nz],x[0])) {
                    que.push_front({x[0],nx,ny,nz});
                }
            }
            else {
                if(chmin(dist[nx][ny][nz],x[0]+1)) {
                    que.push_back({x[0]+1,nx,ny,nz});
                }
            }
        }
    }
    int ans = 1001001001;
    rep(i,4) {
        chmin(ans,dist[gx][gy][i]);
    }
    cout << ans << "\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 70