oj.uz

Submission #899997

# Submission time Handle Problem Language Result Execution time Memory
899997 2024-01-07T12:03:44 Z I_am_Polish_Girl Abracadabra (CEOI22_abracadabra) C++14
10 / 100
 3000 ms 35660 KB 
/*
* powered by ANDRIY POPYK
* in honor of  SEGMENT DECOMPOSITION and N ^ (log(N)) and hate_club_Dasha_Lobas
* I hate GeZhiyuan
* fuck you
*/


#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt")


#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;
typedef long long ll;

#define int long long

int mod = 1000000007;
int inf = 1000000000000000000;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int times_ = 1;

    //cin >> times_;

    while (times_--)
    {
        int n , k;
        cin >> n >> k;

        vector <int> a(n);


        for (int i = 0; i < n; i++)
            cin >> a[i];


        int col = 5500;

        vector <vector <pair <int, int>>> q(col+1);


        vector <int> ans(k , -1);
        for (int i = 0; i < k; i++)
        {
            int t, ind;

            cin >> t >> ind;

            q[min(t , col)].push_back({ ind , i });
        }

        for (int i = 0; i <= col; i++)
        {
            vector <int> b;


            int ind1 = 0;
            int ind2 = n / 2;

            for (int j = 0; j < n; j++)
            {
                if (ind1 == n / 2)
                {
                    b.push_back(a[ind2]);
                    ind2++;
                    continue;
                }

                if (ind2 == n)
                {
                    b.push_back(a[ind1]);
                    ind1++;
                    continue;
                }

                if (a[ind1] < a[ind2])
                {
                    b.push_back(a[ind1]);
                    ind1++;
                    continue;
                }
                else
                {
                    b.push_back(a[ind2]);
                    ind2++;
                    continue;
                }
            }

            for (int j = 0; j < q[i].size(); j++)
            {
                ans[q[i][j].second] = a[q[i][j].first - 1];
            }

            a = b;
            /*
            for (int i = 0; i < n; i++)
                cout << a[i] << " ";
            cout << "\n**\n";

            */
        }


        for (int i = 0; i < k; i++)
            cout << ans[i] << "\n";

        
    }
}

Compilation message

Main.cpp:11: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   11 | #pragma GCC optimization("unroll-loops")
      | 
Main.cpp: In function 'int main()':
Main.cpp:111:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |             for (int j = 0; j < q[i].size(); j++)
      |                             ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 31948 KB Output is correct
2 Correct 164 ms 30240 KB Output is correct
3 Correct 158 ms 29492 KB Output is correct
4 Correct 160 ms 27644 KB Output is correct
5 Correct 174 ms 33060 KB Output is correct
6 Correct 158 ms 31016 KB Output is correct
7 Correct 172 ms 35092 KB Output is correct
8 Correct 154 ms 29256 KB Output is correct
9 Correct 160 ms 28616 KB Output is correct
10 Correct 156 ms 28556 KB Output is correct
11 Correct 154 ms 28356 KB Output is correct
12 Correct 153 ms 27828 KB Output is correct
13 Correct 182 ms 27320 KB Output is correct
14 Correct 160 ms 30820 KB Output is correct
15 Correct 161 ms 28652 KB Output is correct
16 Correct 10 ms 604 KB Output is correct
17 Correct 140 ms 27256 KB Output is correct
18 Correct 167 ms 27036 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2165 ms 35660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3050 ms 6360 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 31948 KB Output is correct
2 Correct 164 ms 30240 KB Output is correct
3 Correct 158 ms 29492 KB Output is correct
4 Correct 160 ms 27644 KB Output is correct
5 Correct 174 ms 33060 KB Output is correct
6 Correct 158 ms 31016 KB Output is correct
7 Correct 172 ms 35092 KB Output is correct
8 Correct 154 ms 29256 KB Output is correct
9 Correct 160 ms 28616 KB Output is correct
10 Correct 156 ms 28556 KB Output is correct
11 Correct 154 ms 28356 KB Output is correct
12 Correct 153 ms 27828 KB Output is correct
13 Correct 182 ms 27320 KB Output is correct
14 Correct 160 ms 30820 KB Output is correct
15 Correct 161 ms 28652 KB Output is correct
16 Correct 10 ms 604 KB Output is correct
17 Correct 140 ms 27256 KB Output is correct
18 Correct 167 ms 27036 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Incorrect 2165 ms 35660 KB Output isn't correct
22 Halted 0 ms 0 KB -