oj.uz

Submission #768615

# Submission time Handle Problem Language Result Execution time Memory
768615 2023-06-28T10:01:51 Z danikoynov Passport (JOI23_passport) C++14
0 / 100
 1 ms 340 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Incorrect 1 ms 324 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Incorrect 1 ms 324 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Incorrect 1 ms 324 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -