oj.uz

Submission #1015554

# Submission time Handle Problem Language Result Execution time Memory
1015554 2024-07-06T13:55:30 Z andrei_iorgulescu Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 3000 ms 5524 KB 
#include <bits/stdc++.h>

using namespace std;

int n,k,a[200005],b[200005],t[200005];
int g;
bool tr[105][105];
vector<int> lol;

int get_who(int x)
{
    int st = -1,pas = 64;
    while (pas != 0)
    {
        if (st + pas < lol.size() and x > lol[st + pas])
            st += pas;
        pas >>= 1;
    }
    return st + 1;
}

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);
    lol = vls;
    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++)
    {
        //cout << get_who(a[i]) << ' ' << get_who(b[i]) << endl;
        if (tr[get_who(a[i])][get_who(b[i])])
            swap(a[i],b[i]);//,cout << i << endl;
    }
    //cout << endl;
}

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];
    g = 1;
    while (g * g * g <= k)
        g++;
    g--;
    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 'int get_who(int)':
fortune_telling2.cpp:15:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         if (st + pas < lol.size() and x > lol[st + pas])
      |             ~~~~~~~~~^~~~~~~~~~~~
fortune_telling2.cpp: In function 'void solve(std::vector<int>)':
fortune_telling2.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < vls.size(); i++)
      |                     ~~^~~~~~~~~~~~
fortune_telling2.cpp:34:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for (int j = 0; j < vls.size(); j++)
      |                         ~~^~~~~~~~~~~~
fortune_telling2.cpp:36:17: warning: unused variable 'x0' [-Wunused-variable]
   36 |             int x0 = vls[i];
      |                 ^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 3 ms 2396 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Correct 3 ms 2392 KB Output is correct
7 Correct 3 ms 2396 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 3 ms 2544 KB Output is correct
12 Correct 3 ms 2396 KB Output is correct
13 Correct 5 ms 2652 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 3 ms 2396 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Correct 3 ms 2392 KB Output is correct
7 Correct 3 ms 2396 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 3 ms 2544 KB Output is correct
12 Correct 3 ms 2396 KB Output is correct
13 Correct 5 ms 2652 KB Output is correct
14 Correct 106 ms 2652 KB Output is correct
15 Correct 284 ms 3160 KB Output is correct
16 Correct 619 ms 3492 KB Output is correct
17 Correct 1012 ms 3820 KB Output is correct
18 Correct 1034 ms 3824 KB Output is correct
19 Correct 948 ms 3676 KB Output is correct
20 Correct 1004 ms 3824 KB Output is correct
21 Correct 694 ms 3804 KB Output is correct
22 Correct 619 ms 3160 KB Output is correct
23 Correct 605 ms 3164 KB Output is correct
24 Correct 669 ms 3160 KB Output is correct
25 Correct 591 ms 3160 KB Output is correct
26 Correct 854 ms 3712 KB Output is correct
27 Correct 1018 ms 3832 KB Output is correct
28 Correct 922 ms 3836 KB Output is correct
29 Correct 977 ms 3816 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 3 ms 2396 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Correct 3 ms 2392 KB Output is correct
7 Correct 3 ms 2396 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 3 ms 2544 KB Output is correct
12 Correct 3 ms 2396 KB Output is correct
13 Correct 5 ms 2652 KB Output is correct
14 Correct 106 ms 2652 KB Output is correct
15 Correct 284 ms 3160 KB Output is correct
16 Correct 619 ms 3492 KB Output is correct
17 Correct 1012 ms 3820 KB Output is correct
18 Correct 1034 ms 3824 KB Output is correct
19 Correct 948 ms 3676 KB Output is correct
20 Correct 1004 ms 3824 KB Output is correct
21 Correct 694 ms 3804 KB Output is correct
22 Correct 619 ms 3160 KB Output is correct
23 Correct 605 ms 3164 KB Output is correct
24 Correct 669 ms 3160 KB Output is correct
25 Correct 591 ms 3160 KB Output is correct
26 Correct 854 ms 3712 KB Output is correct
27 Correct 1018 ms 3832 KB Output is correct
28 Correct 922 ms 3836 KB Output is correct
29 Correct 977 ms 3816 KB Output is correct
30 Correct 1112 ms 4696 KB Output is correct
31 Execution timed out 3061 ms 5524 KB Time limit exceeded
32 Halted 0 ms 0 KB -