oj.uz

Submission #781272

# Submission time Handle Problem Language Result Execution time Memory
781272 2023-07-13T01:41:12 Z Ozy Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 313 ms 40756 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>

#define MAX 1000
//para el vector de querys
#define p second.first
#define id second.second

lli n,q,apu,a,b,t,pos;
lli arr[2][MAX+2];
vector<pair<lli,pll > > querys;
vector<lli> res;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q;
    res.resize(q+2);
    rep(i,1,n) cin >> arr[apu][i];

    rep(i,1,q) {
        cin >> a >> b;
        if (a > n) a = n;
        querys.push_back({a,{b,i}});
    }
    sort(querys.begin(), querys.end());

    pos = 0;
    t = 0;
    while (pos < querys.size()) {
        while (pos < querys.size() && querys[pos].first == t) {
            res[querys[pos].id] = arr[apu][ querys[pos].p ];
            pos++;
        }
        if (pos >= querys.size()) break;

        //debug(t);
        //rep(i,1,n) debugsl(arr[apu][i]);
        //cout << endl;

        //shuffle
        lli a = 1;
        lli b = (n/2)+1;
        lli otro = (apu^1);
        lli cont = 1;

        rep(i,1,n) {

            if (a > (n/2)) {
                arr[otro][cont++] = arr[apu][b];
                b++;
                continue;
            }
            if (b > n) {
                arr[otro][cont++] = arr[apu][a];
                a++;
                continue;
            }

            //escojo el menor entre los 2
            lli soy;
            if (arr[apu][a] < arr[apu][b]) soy = a++;
            else soy = b++;

            arr[otro][cont++] = arr[apu][soy];
        }

        apu = otro;
        t++;
    }

    rep(i,1,q) cout << res[i] << "\n";

    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:39:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     while (pos < querys.size()) {
      |            ~~~~^~~~~~~~~~~~~~~
Main.cpp:40:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         while (pos < querys.size() && querys[pos].first == t) {
      |                ~~~~^~~~~~~~~~~~~~~
Main.cpp:44:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         if (pos >= querys.size()) break;
      |             ~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 35668 KB Output is correct
2 Correct 300 ms 38664 KB Output is correct
3 Correct 279 ms 37280 KB Output is correct
4 Correct 300 ms 37132 KB Output is correct
5 Correct 293 ms 40708 KB Output is correct
6 Correct 272 ms 39252 KB Output is correct
7 Correct 313 ms 40756 KB Output is correct
8 Correct 289 ms 39524 KB Output is correct
9 Correct 275 ms 39172 KB Output is correct
10 Correct 278 ms 39704 KB Output is correct
11 Correct 275 ms 39740 KB Output is correct
12 Correct 267 ms 39300 KB Output is correct
13 Correct 287 ms 39956 KB Output is correct
14 Correct 283 ms 40212 KB Output is correct
15 Correct 306 ms 40740 KB Output is correct
16 Correct 1 ms 320 KB Output is correct
17 Correct 258 ms 39716 KB Output is correct
18 Correct 273 ms 39428 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 320 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 16340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 2004 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 35668 KB Output is correct
2 Correct 300 ms 38664 KB Output is correct
3 Correct 279 ms 37280 KB Output is correct
4 Correct 300 ms 37132 KB Output is correct
5 Correct 293 ms 40708 KB Output is correct
6 Correct 272 ms 39252 KB Output is correct
7 Correct 313 ms 40756 KB Output is correct
8 Correct 289 ms 39524 KB Output is correct
9 Correct 275 ms 39172 KB Output is correct
10 Correct 278 ms 39704 KB Output is correct
11 Correct 275 ms 39740 KB Output is correct
12 Correct 267 ms 39300 KB Output is correct
13 Correct 287 ms 39956 KB Output is correct
14 Correct 283 ms 40212 KB Output is correct
15 Correct 306 ms 40740 KB Output is correct
16 Correct 1 ms 320 KB Output is correct
17 Correct 258 ms 39716 KB Output is correct
18 Correct 273 ms 39428 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 320 KB Output is correct
21 Runtime error 9 ms 16340 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -