oj.uz

Submission #1036771

# Submission time Handle Problem Language Result Execution time Memory
1036771 2024-07-27T16:50:16 Z vjudge1 Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 57800 KB 
#include <iostream>
#include <complex>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <functional>
#include <bitset>
#include <queue>
#include <map>
#include <stack>
#include <cmath>
#include <cstdint>
using namespace std;

#define endl '\n'
#define db double
#define ll __int128
#define int long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;

const int Max = 1e6 + 7, Inf = 1e9 + 7;

void print(bool x) { cout << (x ? "YES" : "NO") << endl; }

string tostring (__int128 x)
{
    string ans = "";
    while(x > 0)
    {
        ans += (x % 10 + '0');
        x /= 10;
    }
    reverse(all(ans));
    return ans;
}

void solve()
{
    int n, q; cin >> n >> q; 
    vector <int> v(n), ans(q, -1); 
    for(auto& u : v) cin >> u; 

    vector <vector<int>> f(n + 1, vector <int> ());
    vector <pair<int, int>> s(q);

    for(int i = 0; i < q; i++){
        cin >> s[i].fs >> s[i].sd;
        s[i].sd--;
        if(s[i].fs <= n){
            f[s[i].fs].push_back(i);
        }
    } 

    _for(i, Inf)
    {
        for(auto& u : f[i]){
            ans[u] = v[s[u].sd];
        }

        vector <int> a, b, c; 

        _for(j, n/2){
            a.push_back(v[j]);
            b.push_back(v[j+n/2]);
        }

        reverse(all(a)); reverse(all(b));

        while (c.size() != n)
        {
            if(a.empty()){
                if(b.size() == n/2){
                    i = Inf+1;
                }
                c.push_back(b.back());
                b.pop_back();
            }else if(b.empty()){
                c.push_back(a.back());
                a.pop_back();
            }else {
                if(a.back() < b.back()){
                    c.push_back(a.back());
                    a.pop_back();
                }else{
                    c.push_back(b.back());
                    b.pop_back();
                }
            }
        }

        swap(c, v);
    }

    _for(i, q) {
        if(ans[i] == -1){
            ans[i] = v[s[i].sd];
        }
        cout << ans[i] << endl;
    }
}

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

    int Q = 1; //cin >> Q;

    while (Q--)
    {
        solve();
    }

    return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:77:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   77 |         while (c.size() != n)
      |                ~~~~~~~~~^~~~
Main.cpp:80:29: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   80 |                 if(b.size() == n/2){
      |                    ~~~~~~~~~^~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 45776 KB Output is correct
2 Correct 203 ms 44112 KB Output is correct
3 Correct 140 ms 42576 KB Output is correct
4 Correct 129 ms 40812 KB Output is correct
5 Correct 144 ms 45292 KB Output is correct
6 Correct 153 ms 44380 KB Output is correct
7 Correct 146 ms 46668 KB Output is correct
8 Correct 134 ms 43088 KB Output is correct
9 Correct 137 ms 42416 KB Output is correct
10 Correct 140 ms 41832 KB Output is correct
11 Correct 143 ms 42116 KB Output is correct
12 Correct 131 ms 39468 KB Output is correct
13 Correct 142 ms 40952 KB Output is correct
14 Correct 137 ms 44372 KB Output is correct
15 Correct 142 ms 42532 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 144 ms 40016 KB Output is correct
18 Correct 131 ms 39860 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 3063 ms 57800 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 3024 ms 12464 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 45776 KB Output is correct
2 Correct 203 ms 44112 KB Output is correct
3 Correct 140 ms 42576 KB Output is correct
4 Correct 129 ms 40812 KB Output is correct
5 Correct 144 ms 45292 KB Output is correct
6 Correct 153 ms 44380 KB Output is correct
7 Correct 146 ms 46668 KB Output is correct
8 Correct 134 ms 43088 KB Output is correct
9 Correct 137 ms 42416 KB Output is correct
10 Correct 140 ms 41832 KB Output is correct
11 Correct 143 ms 42116 KB Output is correct
12 Correct 131 ms 39468 KB Output is correct
13 Correct 142 ms 40952 KB Output is correct
14 Correct 137 ms 44372 KB Output is correct
15 Correct 142 ms 42532 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 144 ms 40016 KB Output is correct
18 Correct 131 ms 39860 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 3063 ms 57800 KB Time limit exceeded
22 Halted 0 ms 0 KB -