竞赛讨论区 > 第三题求hack
头像
Kobe__
发布于 2021-12-31 13:28
+ 关注

第三题求hack

我觉得这个没问题,通过率96%
#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back

using namespace std;
using ll = long long;
using db = double;
using pii = pair<int , int>;

const int mod = 998244353;
const int maxn  = 3e3 + 10;

pii a[maxn];
vector <int> y[maxn];
vector <pii> yy[maxn];
vector <pii> ans[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n, m, k, i, j;
    vector <int> loc;
    cin >> n >> m >> k;
    for (i = 1; i <= k; i++)
    {
        cin >> a[i].first >> a[i].second;
        loc.pb(a[i].first);
    }
    loc.pb(0);
    sort(loc.begin(), loc.end());
    loc.erase(unique(loc.begin(), loc.end()), loc.end());
    for (i = 1; i <= k; i++)
    {
        j = lower_bound(loc.begin(), loc.end(), a[i].first) - loc.begin();
        y[j].pb(a[i].second);
    }
    for (i = 0; i < loc.size(); i++)
    {
        sort(y[i].begin(), y[i].end());
        y[i].erase(unique(y[i].begin(), y[i].end()), y[i].end());
        for (j = 0; j < y[i].size(); j++)
        {
            int l = y[i][j];
            while (j < y[i].size() - 1 && y[i][j] + 1 == y[i][j + 1]) j++;
            int r = y[i][j];
            yy[i].pb({l, r});
        }
    }
    if (loc[0] == 0)
    {
        if (y[0].empty())
        	ans[0].pb({0, m});
        else if (y[0][0] == 0)
        {
            cout << "No";
            return 0;
        }
        else ans[0].pb({0, y[0][0] - 1});
    };

    for (i = 1; i < loc.size(); i++)
    {
        if (loc[i] - loc[i - 1] == 1)
        {
            int k = 0;
            int ld = ans[i - 1][k].first, lu = ans[i - 1][k].second;
            for (j = 0; j < yy[i].size() && k < ans[i - 1].size();)
            {
                int d = yy[i][j].first, u = yy[i][j].second;
                if (d > lu)
                {
                    ans[i].pb({ld, lu}), k++;
                    if (k < ans[i - 1].size())
                        ld = ans[i - 1][k].first, lu = ans[i - 1][k].second;
                    //else break;
                }
                else if (ld > u) j++;
                else if (ld >= d)
                {
                    if (u < lu)
                        ld = u + 1, j++;
                    else 
                    {
                        k++;
                        if (k < ans[i - 1].size())
                            ld = ans[i - 1][k].first, lu = ans[i - 1][k].second;
                       // else break;
                    }
                }
                else
                {
                    ans[i].pb({ld, d - 1});
                    if (lu > u)
                    {
                        ld = u + 1;
                        j++;
                    }
                    else
                    {
                        k++;
                        if (k < ans[i - 1].size())
                            ld = ans[i - 1][k].first, lu = ans[i - 1][k].second;
                        //else break;
                    }
                }

            }
            if (j >= yy[i].size())
            {
                ans[i].pb({ld, lu}), k++;
                for (; k < ans[i - 1].size(); k++)
                    ans[i].pb(ans[i - 1][k]);
            }
        }
        else
        {
            int ld = ans[i - 1][0].first, lu = m;
            for (j = 0; j < yy[i].size() && ld <= lu;)
            {
                int d = yy[i][j].first, u = yy[i][j].second;
                if (u < ld) j++;
                else if (ld >= d)
                {
                    ld = u + 1;
                    j++;
                }
                else
                {
                    ans[i].pb({ld, d - 1});
                    ld = u + 1;
                    j++;
                }
            }
            if (ld <= lu)
                ans[i].pb({ld, lu});
        }
        if (ans[i].empty())
        {
            cout << "No";
            return 0;
        }
        
    }
    if (loc[i - 1] == n)
    {
        if (ans[i - 1][ans[i - 1].size() - 1].second == m)
        	cout << "Yes";
        else cout << "No";
        return 0;
    }
    cout << "Yes";
    return 0;
}


全部评论

(0) 回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐