oj.uz

Submission #1036830

# Submission time Handle Problem Language Result Execution time Memory
1036830 2024-07-27T17:44:13 Z vjudge1 Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 38992 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sort undefined_function // To use stable_sort instead sort 
#define bpc __builtin_popcount
#define ull unsigned long long
#define ld double
#define ll long long
#define mp make_pair
#define F first
#define S second

#pragma GCC optimize("O3")

#ifdef LOCAL 
        #include "debug.h"
#else 
        #define dbg(...) 0
#endif

using namespace __gnu_pbds;
using namespace std;

typedef tree<long long, null_type, less_equal<long long>,
    rb_tree_tag, tree_order_statistics_node_update> Tree;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll INF = 9223372036854775807LL;
const ll inf = 2147483647;
const ll MOD = 998244353; //[998244353, 1e9 + 7, 1e9 + 13]
const ld PI = acos(-1);
const ll NROOT = 800;

ll binpow(ll a, ll b, ll _MOD = -1) {
        if (_MOD == -1)
                _MOD = MOD;
        ll res = 1;
        for (; b; b /= 2, a *= a, a %= _MOD)
                if (b & 1) res *= a, res %= _MOD;
        return res;
}

void set_IO(string s) {
#ifndef LOCAL
        string in  = s +  ".in";
        string out = s + ".out";
        freopen(in.c_str(),  "r",  stdin);
        freopen(out.c_str(), "w", stdout);
#endif
}

bool dataOverflow(ll a, ll b) {return (log10(a) + log10(b) >= 18);}
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a * b / gcd(a, b);}
ll ceil(ll a, ll b) {return (a + b - 1) / b;}
ll invmod(ll a) {return binpow(a, MOD - 2);}

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);

        int n, q;
        cin >> n >> q;

        vector<int> v(n + 1);
        for (int i = 1; i <= n; i ++) 
                cin >> v[i];

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

        for (int i = 1; i <= q; i ++) {
                cin >> qr[i].F.F >> qr[i].F.S;
                qr[i].S = i;
        }

        stable_sort(qr.begin() + 1, qr.end());
        vector<int> ans(q + 1, -1);

        int i1 = 0, i2 = 0;
        int HALF = n / 2;
        vector<int> half1(HALF), half2(HALF);

        int iter = 1;
        for (int i = 0; iter < qr.size(); i ++) {
                while (iter < qr.size() && qr[iter].F.F == i) {
                        ans[qr[iter].S] = v[qr[iter].F.S];
                        iter ++;
                }

                vector<int> prv = v;

                i1 = i2 = 0;
                for (int j = 1; j <= HALF; j ++, i1 ++) 
                       half1[i1] = v[j];
                for (int j = HALF + 1; j <= n; j ++, i2 ++) 
                       half2[i2] = v[j];

                i1 = i2 = 0;
                int tmp = 1;
                while (i1 < HALF && i2 < HALF) {
                        if (half1[i1] < half2[i2]) {
                                v[tmp] = half1[i1];
                                i1 ++;
                        } else {
                                v[tmp] = half2[i2];
                                i2 ++;
                        }

                        tmp ++;
                }

                while (i1 < HALF) {
                        v[tmp] = half1[i1];
                        i1  ++;
                        tmp ++;
                }
                while (i2 < HALF) {
                        v[tmp] = half2[i2];
                        i2  ++;
                        tmp ++;
                }

                if (v == prv)
                        break;
        }

        for (int i = 1; i <= q; i ++) 
                if (ans[qr[i].S] == -1) 
                        ans[qr[i].S] = v[qr[i].F.S];

        for (int i = 1; i <= q; i ++) {
                cout << ans[i] << "\n";
        }

        return 0;
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:84:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for (int i = 0; iter < qr.size(); i ++) {
      |                         ~~~~~^~~~~~~~~~~
Main.cpp:85:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |                 while (iter < qr.size() && qr[iter].F.F == i) {
      |                        ~~~~~^~~~~~~~~~~
Main.cpp: In function 'void set_IO(std::string)':
Main.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         freopen(in.c_str(),  "r",  stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen(out.c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 31568 KB Output is correct
2 Correct 232 ms 31124 KB Output is correct
3 Correct 226 ms 30008 KB Output is correct
4 Correct 216 ms 28804 KB Output is correct
5 Correct 229 ms 30804 KB Output is correct
6 Correct 215 ms 29168 KB Output is correct
7 Correct 229 ms 31056 KB Output is correct
8 Correct 213 ms 29276 KB Output is correct
9 Correct 225 ms 29004 KB Output is correct
10 Correct 217 ms 29516 KB Output is correct
11 Correct 226 ms 29376 KB Output is correct
12 Correct 203 ms 28240 KB Output is correct
13 Correct 230 ms 29264 KB Output is correct
14 Correct 227 ms 30036 KB Output is correct
15 Correct 236 ms 30176 KB Output is correct
16 Correct 0 ms 456 KB Output is correct
17 Correct 185 ms 28700 KB Output is correct
18 Correct 202 ms 28500 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 40.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 31568 KB Output is correct
2 Correct 232 ms 31124 KB Output is correct
3 Correct 226 ms 30008 KB Output is correct
4 Correct 216 ms 28804 KB Output is correct
5 Correct 229 ms 30804 KB Output is correct
6 Correct 215 ms 29168 KB Output is correct
7 Correct 229 ms 31056 KB Output is correct
8 Correct 213 ms 29276 KB Output is correct
9 Correct 225 ms 29004 KB Output is correct
10 Correct 217 ms 29516 KB Output is correct
11 Correct 226 ms 29376 KB Output is correct
12 Correct 203 ms 28240 KB Output is correct
13 Correct 230 ms 29264 KB Output is correct
14 Correct 227 ms 30036 KB Output is correct
15 Correct 236 ms 30176 KB Output is correct
16 Correct 0 ms 456 KB Output is correct
17 Correct 185 ms 28700 KB Output is correct
18 Correct 202 ms 28500 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Execution timed out 3048 ms 38992 KB Time limit exceeded
22 Halted 0 ms 0 KB -