oj.uz

Submission #1015568

# Submission time Handle Problem Language Result Execution time Memory
1015568 2024-07-06T14:19:57 Z andrei_iorgulescu Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 3000 ms 8992 KB 
#include <bits/stdc++.h>

using namespace std;

int n,k,a[200005],b[200005],t[200005];
int g;
bool tr[1005][1005];
vector<int> lol;
int pa[200005],pb[200005];
pair<int,int> vv[400005];
bool sp[200005];
int f1[400005],f2[400005];

void solve(vector<int> op)
{
    set<int> ss;
    for (auto it : op)
        ss.insert(it);
    vector<int> vls;
    for (auto it : ss)
        vls.push_back(it);
    vls.push_back((int)2e9);
    int i0 = 0;
    for (int i = 1; i <= 2 * n; i++)
    {
        while (vls[i0] < f1[i])
            i0++;
        if (f2[i] < 0)
            pb[-f2[i]] = i0;
        else
            pa[f2[i]] = i0;
    }
    for (int i = 0; i < vls.size(); i++)
    {
        for (int j = 0; j < vls.size(); j++)
        {
            int x0 = vls[i];
            int x = vls[i],y = vls[j];
            int cnt_swap = 0;
            for (auto it : op)
            {
                if (it >= x)
                    swap(x,y),cnt_swap ^= 1;
            }
            if (cnt_swap)
                tr[i][j] = true;
            else
                tr[i][j] = false;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if ((!sp[i] and tr[pa[i]][pb[i]]) or (sp[i] and tr[pb[i]][pa[i]]))
            swap(a[i],b[i]),sp[i] ^= 1;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
    for (int i = 1; i <= k; i++)
        cin >> t[i];
    for (int i = 1; i <= n; i++)
    {
        vv[2 * i - 1] = {a[i],i};
        vv[2 * i] = {b[i],-i};
    }
    sort(vv + 1,vv + 2 * n + 1);
    for (int i = 1; i <= 2 * n; i++)
    {
        f1[i] = vv[i].first;
        f2[i] = vv[i].second;
    }
    g = 100;
    for (int i = 1; i <= k; i += g)
    {
        vector<int> op;
        for (int j = i; j <= k and j < i + g; j++)
            op.push_back(t[j]);
        solve(op);
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++)
        ans += a[i];
    cout << ans;
    return 0;
}

Compilation message

fortune_telling2.cpp: In function 'void solve(std::vector<int>)':
fortune_telling2.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0; i < vls.size(); i++)
      |                     ~~^~~~~~~~~~~~
fortune_telling2.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for (int j = 0; j < vls.size(); j++)
      |                         ~~^~~~~~~~~~~~
fortune_telling2.cpp:37:17: warning: unused variable 'x0' [-Wunused-variable]
   37 |             int x0 = vls[i];
      |                 ^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 604 KB Output is correct
2 Correct 9 ms 8700 KB Output is correct
3 Correct 9 ms 8540 KB Output is correct
4 Correct 15 ms 8700 KB Output is correct
5 Correct 9 ms 4604 KB Output is correct
6 Correct 10 ms 604 KB Output is correct
7 Correct 14 ms 8700 KB Output is correct
8 Correct 11 ms 8540 KB Output is correct
9 Correct 10 ms 600 KB Output is correct
10 Correct 9 ms 8540 KB Output is correct
11 Correct 10 ms 8540 KB Output is correct
12 Correct 10 ms 8536 KB Output is correct
13 Correct 13 ms 8540 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 604 KB Output is correct
2 Correct 9 ms 8700 KB Output is correct
3 Correct 9 ms 8540 KB Output is correct
4 Correct 15 ms 8700 KB Output is correct
5 Correct 9 ms 4604 KB Output is correct
6 Correct 10 ms 604 KB Output is correct
7 Correct 14 ms 8700 KB Output is correct
8 Correct 11 ms 8540 KB Output is correct
9 Correct 10 ms 600 KB Output is correct
10 Correct 9 ms 8540 KB Output is correct
11 Correct 10 ms 8540 KB Output is correct
12 Correct 10 ms 8536 KB Output is correct
13 Correct 13 ms 8540 KB Output is correct
14 Correct 113 ms 8796 KB Output is correct
15 Correct 245 ms 8896 KB Output is correct
16 Correct 470 ms 2152 KB Output is correct
17 Correct 678 ms 8992 KB Output is correct
18 Correct 683 ms 8992 KB Output is correct
19 Correct 700 ms 7260 KB Output is correct
20 Correct 670 ms 8992 KB Output is correct
21 Correct 631 ms 2616 KB Output is correct
22 Correct 424 ms 8992 KB Output is correct
23 Correct 400 ms 8992 KB Output is correct
24 Correct 404 ms 8792 KB Output is correct
25 Correct 385 ms 8796 KB Output is correct
26 Correct 537 ms 8972 KB Output is correct
27 Correct 605 ms 8988 KB Output is correct
28 Correct 551 ms 8796 KB Output is correct
29 Correct 620 ms 8796 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 604 KB Output is correct
2 Correct 9 ms 8700 KB Output is correct
3 Correct 9 ms 8540 KB Output is correct
4 Correct 15 ms 8700 KB Output is correct
5 Correct 9 ms 4604 KB Output is correct
6 Correct 10 ms 604 KB Output is correct
7 Correct 14 ms 8700 KB Output is correct
8 Correct 11 ms 8540 KB Output is correct
9 Correct 10 ms 600 KB Output is correct
10 Correct 9 ms 8540 KB Output is correct
11 Correct 10 ms 8540 KB Output is correct
12 Correct 10 ms 8536 KB Output is correct
13 Correct 13 ms 8540 KB Output is correct
14 Correct 113 ms 8796 KB Output is correct
15 Correct 245 ms 8896 KB Output is correct
16 Correct 470 ms 2152 KB Output is correct
17 Correct 678 ms 8992 KB Output is correct
18 Correct 683 ms 8992 KB Output is correct
19 Correct 700 ms 7260 KB Output is correct
20 Correct 670 ms 8992 KB Output is correct
21 Correct 631 ms 2616 KB Output is correct
22 Correct 424 ms 8992 KB Output is correct
23 Correct 400 ms 8992 KB Output is correct
24 Correct 404 ms 8792 KB Output is correct
25 Correct 385 ms 8796 KB Output is correct
26 Correct 537 ms 8972 KB Output is correct
27 Correct 605 ms 8988 KB Output is correct
28 Correct 551 ms 8796 KB Output is correct
29 Correct 620 ms 8796 KB Output is correct
30 Correct 2013 ms 8796 KB Output is correct
31 Execution timed out 3062 ms 8844 KB Time limit exceeded
32 Halted 0 ms 0 KB -