ABC E 求hack
  • 板块题目总版
  • 楼主__vector__
  • 当前回复8
  • 已保存回复9
  • 发布时间2024/1/27 21:43
  • 上次更新2024/1/28 01:13:55
查看原帖
ABC E 求hack
507348
__vector__楼主2024/1/27 21:43

参照了快速排序的思想,每次随机中点并分治。
TLE 6 AC 25

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define REP(i, a, b) for (int i = a; i >= b; i--)
#define pb push_back
#define eb emplace_back
#define popcount __builtin_popcount
#define ctz __builtin_ctz
#define gc getchar()
#define mkpr make_pair
#define i128 __int128
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int, int> pii;
typedef std::pair<ll, ll> pll;
template <class T>
void write(T x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x >= 10)
    {
        write(x / 10);
    }
    putchar(x % 10 ^ 48);
}
template <class T>
void read(T &x)
{
    x = 0;
    T f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    x *= f;
}
template <class T>
T quick_pow(T a, T b, T p = -1)
{
    if (p == -1)
    {
        T res = 1;
        while (b)
        {
            if (b & 1)
                res = res * a;
            a *= a;
            b >>= 1;
        }
        return res;
    }
    else
    {
        T res = 1;
        while (b)
        {
            if (b & 1)
                res = res * a % p;
            a = a * a % p;
            b >>= 1;
        }
        return res;
    }
}
template <class T>
T inv(T x, T p) { return quick_pow(x, p - 2, p); }
ll qpow(ll a, ll b, ll mod)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
ll invll(ll a, ll mod)
{
    return qpow(a, mod - 2, mod);
}
struct Matrix
{
    vector<vector<ll>> mp;
    ll p;
    int size;
    // 第二个参数:是否设为单位矩阵
    void init(int siz, ll mod = -1, bool isdw = 0)
    {
        p = mod;
        size = siz;
        mp.resize(siz);
        for (int i = 0; i < siz; i++)
        {
            mp[i].resize(siz);
            for (int j = 0; j < siz; j++)
            {
                mp[i][j] = 0;
            }
            if (isdw)
                mp[i][i] = 1;
        }
    }
    Matrix operator*(const Matrix &b)
    {
        Matrix res;
        res.init(max(size, b.size), p);
        for (int i = 0; i < size; i++)
        {
            for (int k = 0; k < size; k++)
            {
                for (int j = 0; j < size; j++)
                {
                    if (k >= b.size || j >= b.size)
                    {
                        continue;
                    }
                    res.mp[i][j] += mp[i][k] * b.mp[k][j];
                    if (res.p != -1)
                        res.mp[i][j] %= res.p;
                }
            }
        }
        return res;
    }
};
Matrix quick_pow_mat(Matrix a, ll b)
{
    Matrix res;
    res.init(a.size, a.p, 1);
    while (b)
    {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
mt19937 rnd(random_device{}());
template <const int mod>
class static_mint
{
public:
    int mval = 0, minv = -1;
    static_mint()
    {
        mval = 0;
        minv = -1;
    }
    static_mint(int val)
    {
        this->mval = val % mod;
        this->minv = -1;
    }
    int val()
    {
        return mval;
    }
    int inv()
    {
        if (minv != -1)
            return minv;
        else
            return minv = qpow(mval, mod - 2, mod);
    }
    static_mint operator=(int b)
    {
        this->mval = b % mod;
        this->minv = -1;
        return *this;
    }
    operator int()
    {
        return int(mval);
    }
    operator ll()
    {
        return ll(mval);
    }
    operator double()
    {
        return (double)(mval);
    }
    operator float()
    {
        return (float)(mval);
    }
    bool operator!=(static_mint b)
    {
        return mval != b.val();
    }
    static_mint operator+(static_mint b)
    {
        return static_mint((1ll * mval + b.val()) % (ll)mod);
    }
    static_mint operator-(static_mint b)
    {
        int res = (1ll * mval - b.val()) % (ll)mod + mod;
        if (res >= mod)
            res -= mod;
        return static_mint(res);
    }
    static_mint operator*(static_mint b)
    {
        int res = 1ll * mval * b.val() % (ll)mod;
        return static_mint(res);
    }
    static_mint operator/(static_mint b)
    {
        int res = 1ll * mval * b.inv() % (ll)mod;
        return static_mint(res);
    }
    static_mint operator+=(static_mint b)
    {
        mval = (1ll * mval + b.val()) % (ll)mod;
        minv = -1;
        return *this;
    }
    static_mint operator-=(static_mint b)
    {
        mval = (1ll * mval - b.val()) % (ll)mod + mod;
        if (mval >= mod)
            mval -= mod;
        minv = -1;
        return *this;
    }
    static_mint operator*=(static_mint b)
    {
        mval = 1ll * mval * b.val() % (ll)mod;
        minv = -1;
        return *this;
    }
    static_mint operator/=(static_mint b)
    {
        mval = 1ll * mval * b.inv() % (ll)mod;
        minv = -1;
        return *this;
    }
    // ===========================
    // b's type = int
    static_mint operator+(int b)
    {
        return static_mint((1ll * mval + b) % (ll)mod);
    }
    static_mint operator-(int b)
    {
        int res = (1ll * mval - b) % (ll)mod + mod;
        if (res >= mod)
            res -= mod;
        return static_mint(res);
    }
    static_mint operator*(int b)
    {
        int res = 1ll * mval * b % (ll)mod;
        return static_mint(res);
    }
    static_mint operator/(int b)
    {
        int res = 1ll * mval * invll(b, mod) % (ll)mod;
        return static_mint(res);
    }
    static_mint operator+=(int b)
    {
        mval = (1ll * mval + b) % (ll)mod;
        minv = -1;
        return *this;
    }
    static_mint operator-=(int b)
    {
        mval = (1ll * mval - b) % (ll)mod + mod;
        if (mval >= mod)
            mval -= mod;
        minv = -1;
        return *this;
    }
    static_mint operator*=(int b)
    {
        mval = 1ll * mval * b % (ll)mod;
        minv = -1;
        return *this;
    }
    static_mint operator/=(int b)
    {
        mval = 1ll * mval * invll(b, mod) % (ll)mod;
        minv = -1;
        return *this;
    }
    bool operator!=(int b)
    {
        return mval != b;
    }
};
const int maxn = 2e5 + 5;
struct Edge
{
    int a, b;
} edge[maxn];
int n;
deque<Edge> lef, rig;
bool QuickSort(int l, int r)
{
    if (r - l + 1 <= 1)
        return 0;
    int mid = l+rnd()%(r-l+1);
    int midl = edge[mid].a, midr = edge[mid].b;
    if (midl > midr)
        swap(midl, midr);
    auto temp = edge[mid];
    FOR(i, l, r)
    {
        if (i == mid)
            continue;
        if (edge[i].a >= midl && edge[i].a <= midr)
        {
            if (!(edge[i].b >= midl && edge[i].b <= midr))
            {
                puts("Yes");
            exit(0);
                //      printf("1 %d %d pd = %d\n",l,r,i);
                return 1;
            }
            else
            {
                lef.push_back(edge[i]);
            }
        }
        else
        {
            if ((edge[i].b >= midl && edge[i].b <= midr))
            {
                puts("Yes");
            exit(0);
                //        printf("2 %d %d pd = (%d,%d) mid = (%d,%d)\n",l,r,edge[i].a,edge[i].b,edge[mid].a,edge[mid].b);
                return 1;
            }
            else
            {
                rig.push_back(edge[i]);
            }
        }
    }
    int point = l;
    while (!lef.empty())
    {
        edge[point++] = lef.front();
        lef.pop_front();
    }
    int midp = point;
    edge[point++] = temp;
    while (!rig.empty())
    {
        edge[point++] = rig.front();
        rig.pop_front();
    }
    if (rnd() & 1)
    {
        if (QuickSort(midp + 1, r))
        {
            puts("Yes");
            exit(0);
        }
        if (QuickSort(l, midp - 1))
        {
            puts("Yes");
            exit(0);
        }
    }
    else
    {
        if (QuickSort(l, midp - 1))
        {
            puts("Yes");
            exit(0);
        }
        if (QuickSort(midp + 1, r))
        {
            puts("Yes");
            exit(0);
        }
    }

    return 0;
}
int main()
{
    scanf("%d", &n);
    FOR(i, 1, n)
    {
        scanf("%d%d", &edge[i].a, &edge[i].b);
    }
    random_shuffle(edge+1,edge+n+1);
    puts(QuickSort(1, n) ? "Yes" : "No");
    return 0;
}  
2024/1/27 21:43
加载中...