Submission #768615

#	Time	Username	Problem	Language	Result	Execution time	Memory
768615		danikoynov	Passport (JOI23_passport)	C++14	0 / 100	1 ms	340 KiB

passport

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 2.5e3 + 10;

int n, q, l[maxn], r[maxn];
int dp[maxn][maxn];
int used[maxn];
int rec(int i, int j)
{
    bool done = false;
    for (int p = i; p <= j; p ++)
        if (!used[p])
    {
        done = true;
        break;
    }
    if (done)
        return 0;

        if (dp[i][j] != 0)
            return dp[i][j];
        int ans = 1e9;
    for (int pos = i; pos <= j; pos ++)
    {
        if (l[pos] >= i && r[pos] <= j)
            continue;

        ans = min(ans, 1 + rec(min(i, l[pos]), max(j, r[pos])));
    }
    return (dp[i][j] = ans);
}
void action(int x)
{

        int ans = rec(x, x);
        if (ans > n)
        cout << -1 << endl;
        else
            cout << ans << endl;
}

struct interval
{
    int idx, l, r;
};

bool cmp(const interval &a, const interval &b)
{
    if (a.l == b.l)
        return a.r > b.r;
    return a.l < b.l;
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> l[i] >> r[i];
    }

    int nec = n;
    vector < int > imp;
    vector < interval > vec;
    for (int i = 1; i <= n; i ++)
    {
        interval cur;
        cur.l = l[i];
        cur.r = r[i];
        cur.idx = i;
        vec.push_back(cur);
    }

    sort(vec.begin(), vec.end(), cmp);
    int to = 0;
    bool fck = false;
    for (int i = 0; i < vec.size(); i ++)
    {
        interval cur = vec[i];
        if (to < cur.l && to != 0)
            fck = true;
        if (cur.r > to)
            to = cur.r, imp.push_back(cur.idx);
        else
        used[cur.idx] = 1, nec --;
    }

    cin >> q;
    if (fck)
    {
        for (int i = 1; i <= q; i ++)
            cout << -1 << endl;
        return;
    }

    for (int i = 1; i <= q; i ++)
    {
        int x;
        cin >> x;
        int ans = rec(x, x);
        ///cout << ans << endl;
        if (ans > n)
        cout << -1 << endl;
        else
        {
            if (nec == 1)
                cout << ans << endl;
            else
            cout << nec + ans << endl;
        }
    }



}

int main()
{
    speed();
    solve();
    return 0;
}

Compilation message (stderr)

passport.cpp: In function 'int rec(int, int)':
passport.cpp:28:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   28 |     if (done)
      |     ^~
passport.cpp:31:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   31 |         if (dp[i][j] != 0)
      |         ^~
passport.cpp: In function 'void solve()':
passport.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<interval>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int i = 0; i < vec.size(); i ++)
      |                     ~~^~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46