Submission #1015554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015554		andrei_iorgulescu	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	35 / 100	3061 ms	5524 KiB

fortune_telling2

#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 (stderr)

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 / 4
• Subtask 2: 31 / 31
• Subtask 3: 0 / 65