oj.uz

Submission #729991

# Submission time Handle Problem Language Result Execution time Memory
729991 2023-04-25T03:02:15 Z baojiaopisu Abracadabra (CEOI22_abracadabra) C++14
10 / 100
 3000 ms 50372 KB 
#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;

#define fi first
#define se second
#define left BAO
#define right ANH
#define pb push_back
#define pf push_front
#define mp make_pair
#define ins insert
#define btpc __builtin_popcount
#define btclz __builtin_clz

#define sz(x) (int)(x.size());
#define all(x) x.begin(), x.end()
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y)
        {
            x = y;
            return true;
        }
        return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y)
        {
            x = y;
            return true;
        }
        return false;
    }

const int MOD = 1e9 + 7; //998244353

template<class X, class Y>
	void add(X &x, const Y &y) {
		x = (x + y);
		if(x >= MOD) x -= MOD;
	}

template<class X, class Y> 
	void sub(X &x, const Y &y) {
		x = (x - y);
		if(x < 0) x += MOD;
	}

/* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/

const ll INF = 1e9;
const int N = 1e6 + 10;

int a[N], b[N], ans[N];
vector<pii> query[N];

void BaoJiaoPisu() {
	int n, q; cin >> n >> q;
	for(int i = 1; i <= n; i++) cin >> a[i];
	
	for(int i = 1; i <= q; i++) {
		int t, c; cin >> t >> c;
		minimize(t, n);
		if(t == 0) ans[i] = a[c];
		query[t].pb(mp(c, i));
	}	

	int it = 0;
	while(true) {
		++it;
		int i = 1, j = n / 2 + 1;
		int curr = 0;
		while(i <= n / 2 || j <= n) {
			if(i > n / 2) b[++curr] = a[j++];
			else if(j > n) b[++curr] = a[i++];
			else if(a[i] < a[j]) b[++curr] = a[i++];
			else b[++curr] = a[j++];
		}

		bool ok = true;
		for(int i = 1; i <= n; i++) {
			ok &= (a[i] == b[i]);
			a[i] = b[i];
		}

		for(auto x : query[it]) {
			ans[x.se] = a[x.fi];
		}
		if(ok) break;
	}

	if(it < n) {
		for(auto x : query[n]) {
			ans[x.se] = a[x.fi];
		}
	}

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

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

    int tc = 1, ddd = 0;
    // cin >> tc;
    while(tc--) {
        //ddd++;
        //cout << "Case #" << ddd << ": ";
        BaoJiaoPisu();
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:125:17: warning: unused variable 'ddd' [-Wunused-variable]
  125 |     int tc = 1, ddd = 0;
      |                 ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 49624 KB Output is correct
2 Correct 234 ms 48156 KB Output is correct
3 Correct 207 ms 47464 KB Output is correct
4 Correct 208 ms 46236 KB Output is correct
5 Correct 230 ms 49408 KB Output is correct
6 Correct 206 ms 49200 KB Output is correct
7 Correct 221 ms 50372 KB Output is correct
8 Correct 200 ms 48096 KB Output is correct
9 Correct 206 ms 46708 KB Output is correct
10 Correct 209 ms 46756 KB Output is correct
11 Correct 198 ms 47080 KB Output is correct
12 Correct 195 ms 44448 KB Output is correct
13 Correct 204 ms 45788 KB Output is correct
14 Correct 201 ms 48692 KB Output is correct
15 Correct 215 ms 46356 KB Output is correct
16 Correct 11 ms 23892 KB Output is correct
17 Correct 186 ms 44644 KB Output is correct
18 Correct 192 ms 44480 KB Output is correct
19 Correct 12 ms 23824 KB Output is correct
20 Correct 12 ms 23816 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3021 ms 47768 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 3039 ms 28808 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 49624 KB Output is correct
2 Correct 234 ms 48156 KB Output is correct
3 Correct 207 ms 47464 KB Output is correct
4 Correct 208 ms 46236 KB Output is correct
5 Correct 230 ms 49408 KB Output is correct
6 Correct 206 ms 49200 KB Output is correct
7 Correct 221 ms 50372 KB Output is correct
8 Correct 200 ms 48096 KB Output is correct
9 Correct 206 ms 46708 KB Output is correct
10 Correct 209 ms 46756 KB Output is correct
11 Correct 198 ms 47080 KB Output is correct
12 Correct 195 ms 44448 KB Output is correct
13 Correct 204 ms 45788 KB Output is correct
14 Correct 201 ms 48692 KB Output is correct
15 Correct 215 ms 46356 KB Output is correct
16 Correct 11 ms 23892 KB Output is correct
17 Correct 186 ms 44644 KB Output is correct
18 Correct 192 ms 44480 KB Output is correct
19 Correct 12 ms 23824 KB Output is correct
20 Correct 12 ms 23816 KB Output is correct
21 Execution timed out 3021 ms 47768 KB Time limit exceeded
22 Halted 0 ms 0 KB -