Submission #867779

#	Time	Username	Problem	Language	Result	Execution time	Memory
867779		mariaclara	Abracadabra (CEOI22_abracadabra)	C++17	10 / 100	3074 ms	41544 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pii;
const int MAXN = 2e5+10;
const int MAXQ = 1e6+10;
const int MOD = 1e9+7;
#define all(x) x.begin(), x.end()
#define mk make_pair
#define pb push_back
#define f first
#define s second

int n, m, v[MAXN], a[MAXN], resp[MAXQ];
vector<pair<pii,int>> queries;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

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

    for(int i = 1, a, b; i <= m; i++) {
        cin >> a >> b;
        queries.pb({{a,b},i});
    }

    sort(all(queries));

    bool mudou = 1;
    for(int i = 0, cnt = 0; mudou; i++) {
        for(; cnt < queries.size(); cnt++) {
            if(queries[cnt].f.f == i) resp[queries[cnt].s] = v[queries[cnt].f.s];
            else break;
        }
        if(cnt > queries.size()) break;

        mudou = 0;
        for(int j = 1; j <= n; j++)
            a[j] = v[j];

        int l=1, r=n/2+1;
        for( ; l <= n/2 and r <= n; ) {
            if(a[l] < a[r]) v[l+r-n/2-1] = a[l], l++;
            else v[l+r-n/2-1] = a[r], r++;
        }
        while(l <= n/2) v[l+r-n/2-1] = a[l], l++;
        while(r <= n) v[l+r-n/2-1] = a[r], r++;

        for(int j = 1; j <= n; j++){
            if(v[j] != a[j]) mudou = 1;
        }
    }

    for(int i = 0; i < queries.size(); i++) {
        if(resp[queries[i].s] == 0) resp[queries[i].s] = v[queries[i].f.s];
    }

    for(int i = 1; i <= m; i++)
        cout << resp[i] << "\n";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(; cnt < queries.size(); cnt++) {
      |               ~~~~^~~~~~~~~~~~~~~~
Main.cpp:40:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         if(cnt > queries.size()) break;
      |            ~~~~^~~~~~~~~~~~~~~~
Main.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i = 0; i < queries.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25