Submission #1220220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220220		ainta	IOI Fever (JOI21_fever)	C++20	37 / 100	5092 ms	4388 KiB

fever

#include <bits/stdc++.h>
using namespace std;
 
#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;
 
ll rand_int(ll l, ll r) { //[l, r]
	#ifdef LOCAL
	static mt19937_64 gen;
	#else
    static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
    #endif
    return uniform_int_distribution<ll>(l, r)(gen);
}
 
 
template <uint MD> struct ModInt {
    using M = ModInt;
    const static M G;
    uint v;
    ModInt(ll _v = 0) { set_v(_v % MD + MD); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(ull(v) * r.v % MD); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<998244353>;
template<> const Mint Mint::G = Mint(3);
 
template <class Mint> void nft(bool type, vc<Mint>& a) {
    int n = int(a.size()), s = 0;
    while ((1 << s) < n) s++;
    assert(1 << s == n);
 
    static vc<Mint> ep, iep;
    while (int(ep.size()) <= s) {
        ep.push_back(Mint::G.pow(Mint(-1).v / (1 << ep.size())));
        iep.push_back(ep.back().inv());
    }
    vc<Mint> b(n);
    for (int i = 1; i <= s; i++) {
        int w = 1 << (s - i);
        Mint base = type ? iep[i] : ep[i], now = 1;
        for (int y = 0; y < n / 2; y += w) {
            for (int x = 0; x < w; x++) {
                auto l = a[y << 1 | x];
                auto r = now * a[y << 1 | x | w];
                b[y | x] = l + r;
                b[y | x | n >> 1] = l - r;
            }
            now *= base;
        }
        swap(a, b);
    }
}

 
template <class Mint> vc<Mint> multiply(const vc<Mint>& a, const vc<Mint>& b) {
    int n = int(a.size()), m = int(b.size());
    if (!n || !m) return {};
    if(n<30 || m<30){
        vc<Mint> ret(n+m-1);
        rep(i,n)rep(j,m)ret[i+j] += a[i]*b[j];
        return ret;
    }
    int lg = 0;
    while ((1 << lg) < n + m - 1) lg++;
    int z = 1 << lg;
    auto a2 = a, b2 = b;
    a2.resize(z);
    b2.resize(z);
    nft(false, a2);
    nft(false, b2);
    for (int i = 0; i < z; i++) a2[i] *= b2[i];
    nft(true, a2);
    a2.resize(n + m - 1);
    Mint iz = Mint(z).inv();
    for (int i = 0; i < n + m - 1; i++) a2[i] *= iz;
    return a2;
}
using t4 = tuple<int,int,int,int>;
using t5 = tuple<int,int,int,int,int>;
 
#define N_ 110000
const int SZ = (1<<19);

int n;
int D[N_][4];
int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};
struct point{
    int x, y;
}w[N_];
priority_queue<array<int,3>>PQ;
void Put(int a, int ck, int d){
    if(D[a][ck]<=d)return;
    D[a][ck]=d;
    PQ.push({-d,a,ck});
}
int Go(int st_dir){
    rng(i,1,n){
        rep(j,4){
            D[i][j]=2e9;
        }
    }
    Put(1,st_dir,0);
    while(!PQ.empty()){
        auto [d,a,ck] = PQ.top();
        PQ.pop();
        d=-d;
        if(D[a][ck]!=d)continue;
        rng(i,1,n){
            if(a==i)continue;
            int d2 = (abs(w[a].x-w[i].x) + abs(w[a].y-w[i].y))/2;
            if(d2<d)continue;
            if(w[a].y == w[i].y){
                if(ck==0 && w[a].x < w[i].x) Put(i,ck^2,d2);
                if(ck==2 && w[a].x > w[i].x) Put(i,ck^2,d2);
            }
            if(w[a].x == w[i].x){
                if(ck==1 && w[a].y < w[i].y) Put(i,ck^2,d2);
                if(ck==3 && w[a].y > w[i].y) Put(i,ck^2,d2);
            }
            if(w[a].x+w[a].y == w[i].x+w[i].y){
                int ck2 = ck^1;
                if(ck==0 && w[a].x < w[i].x) Put(i,ck2,d2);
                if(ck==1 && w[a].x > w[i].x) Put(i,ck2,d2);
                if(ck==2 && w[a].x > w[i].x) Put(i,ck2,d2);
                if(ck==3 && w[a].x < w[i].x) Put(i,ck2,d2);
            }
            if(w[a].x-w[a].y == w[i].x-w[i].y && abs(w[a].x-w[i].x) >= d){
                int ck2 = ck^3;
                if(ck==0 && w[a].x < w[i].x) Put(i,ck2,d2);
                if(ck==1 && w[a].x < w[i].x) Put(i,ck2,d2);
                if(ck==2 && w[a].x > w[i].x) Put(i,ck2,d2);
                if(ck==3 && w[a].x > w[i].x) Put(i,ck2,d2);
            }
        }
    }
    int res=0;
    rng(i,1,n){
        int ck=0;
        rep(j,4){
            if(D[i][j]<1.1e9)ck=1;
        }
        res+=ck;
    }
    return res;
}
void Solve(){
    scanf("%d",&n);
    rng(i,1,n){
        scanf("%d%d",&w[i].x,&w[i].y);
        w[i].x*=2,w[i].y*=2;
    }
    int ans=0;
    rep(i,4){
        ans=max(ans,Go(i));
    }
    printf("%d\n",ans);
}

int main(){
	//init();
	int TC=1;
	//scanf("%d",&TC);
	while(TC--){
		Solve();
	}
}

Compilation message (stderr)

fever.cpp: In function 'void Solve()':
fever.cpp:193:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  193 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
fever.cpp:195:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  195 |         scanf("%d%d",&w[i].x,&w[i].y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 12 / 12
• Subtask 6: 0 / 32
• Subtask 7: 0 / 31