oj.uz

답안 #709078

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
709078 2023-03-13T05:59:56 Z vjudge1 Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 35636 KB 
//Bismillahir-Rahmanir-Rahim

#include <bits/stdc++.h>
/*#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")*/

#define Respa return
#define gold 0

#define pb push_back
#define pii pair <int, int>
#define pll pair <long long, long long>
#define ll long long
#define ld long double
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define sz(s) (int)s.size()
#define skip continue
#define bpop(x) (ll)__builtin_popcountll(x)

using namespace std;

const int N = 1e6 + 7;
const int K = 5e2 + 7;
const int MAXA = 5e4 + 7;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const ll MOD = (1ll << 30);

pii dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

#define int long long

int n, q, a[N], b[N], ans[N];
void f() {
    vector <int> av, bv;
    for (int i = 1;i <= n / 2;i++)av.pb(a[i]);
    for (int i = n / 2 + 1;i <= n;i++)bv.pb(a[i]);
    av.pb(INF), bv.pb(INF);
    int l = 0, r = 0, pos = 0;
    while (l < n / 2 || r < n / 2) {
        if (av[l] <= bv[r])b[++pos] = av[l++];
        else b[++pos] = bv[r++];
    }
    for (int i = 1;i <= n;i++)a[i] = b[i];// cout << b[i] << ' ';
    //cout << '\n';
}
void solve() {
    cin >> n >> q;
    vector <pair <pii, int>> qs;
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= q;i++) {
        int t, p;
        cin >> t >> p;
        qs.pb({{t, p}, i});
    }
    sort(all(qs));
    int last = 0;
    for (int i = 0;i < q;i++) {
        int t = qs[i].x.x, pos = qs[i].x.y, id = qs[i].y;
        if (t - last == 0)ans[id] = a[pos];
        else {
            if (t > n)ans[id] = a[pos];
            else {
                int x = t - last;
                while (x--)f();
                ans[id] = a[pos];
            }
        }
        last = t;
    }
    for (int i = 1;i <= q;i++)cout << ans[i] << '\n';
}
signed main() {
    //srand(time(NULL));
    //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("G.in", "r", stdin);
    //freopen("G.out", "w", stdout);
    int test = 1;
    //cin >> test;
    for (int i = 1;i <= test;i++) {
        //cout << "Case " << i << ": ";
        solve();
    }
    Respa gold;//2022-2023 InshAllah
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 340 ms 35600 KB Output is correct
2 Correct 368 ms 35636 KB Output is correct
3 Correct 317 ms 34176 KB Output is correct
4 Correct 315 ms 34000 KB Output is correct
5 Correct 337 ms 35432 KB Output is correct
6 Correct 322 ms 33928 KB Output is correct
7 Correct 353 ms 35536 KB Output is correct
8 Correct 350 ms 34240 KB Output is correct
9 Correct 313 ms 33860 KB Output is correct
10 Correct 337 ms 34540 KB Output is correct
11 Correct 324 ms 34432 KB Output is correct
12 Correct 339 ms 34088 KB Output is correct
13 Correct 345 ms 34864 KB Output is correct
14 Correct 369 ms 35016 KB Output is correct
15 Correct 320 ms 35536 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 298 ms 34448 KB Output is correct
18 Correct 313 ms 34216 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3049 ms 29544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3054 ms 6336 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 340 ms 35600 KB Output is correct
2 Correct 368 ms 35636 KB Output is correct
3 Correct 317 ms 34176 KB Output is correct
4 Correct 315 ms 34000 KB Output is correct
5 Correct 337 ms 35432 KB Output is correct
6 Correct 322 ms 33928 KB Output is correct
7 Correct 353 ms 35536 KB Output is correct
8 Correct 350 ms 34240 KB Output is correct
9 Correct 313 ms 33860 KB Output is correct
10 Correct 337 ms 34540 KB Output is correct
11 Correct 324 ms 34432 KB Output is correct
12 Correct 339 ms 34088 KB Output is correct
13 Correct 345 ms 34864 KB Output is correct
14 Correct 369 ms 35016 KB Output is correct
15 Correct 320 ms 35536 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 298 ms 34448 KB Output is correct
18 Correct 313 ms 34216 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Execution timed out 3049 ms 29544 KB Time limit exceeded
22 Halted 0 ms 0 KB -