Submission #1159978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159978		AgentPengin	Bubble Sort 2 (JOI18_bubblesort2)	C++20	60 / 100	5951 ms	4420 KiB

bubblesort2

/**
 *    author:  AgentPengin ( Độc cô cầu bại )
 *    created: 23.12.2022 10:08:02
 *    too lazy to update time
**/
#include<bits/stdc++.h>
#include"bubblesort2.h"

#define EL '\n'
#define fi first
#define se second
#define NAME "TASK"
#define ll long long
#define lcm(a,b) (a/gcd(a,b))*b
#define db(val) "["#val" = " << (val) << "] "
#define bend(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define ex exit(0)

using namespace std;

const ll mod = 1e9 + 7;
const int inf = 0x1FFFFFFF;
const int MAXN = 1e5 + 5;

vector<int> countScans(vector<int> a, vector<int> x, vector<int> v) {
	int n = sz(a), q = sz(x);
	vector<int> ans(q, 0);
	if (n <= 2000 && q <= 2000) {
		for (int i = 0;i < q;i++) {
			a[x[i]] = v[i];
			vector<int> A = a;
			while(true) {
				bool swapped = false;
				for (int i = 1;i < n;i++) {
					if (A[i - 1] > A[i]) {
						swap(A[i - 1], A[i]);
						swapped = true;
					}
				}
				if (!swapped) break;
				ans[i]++;
			}			
		}
		return ans;
	} else if (n <= 8000 && q <= 8000) {
		vector<int> p(n);
		iota(bend(p), 0);
		for (int i = 0;i < q;i++) {
			a[x[i]] = v[i];
			sort(bend(p), [&](int u, int v){
				return a[u] < a[v] || (a[u] == a[v] && u < v);
			});
			for (int j = 0;j < n;j++) {
				ans[i] = max(ans[i], p[j] - j);
			}
		}
		return ans;
	} else if (n <= 50000 && q <= 50000 && *max_element(bend(a)) <= 100 && *max_element(bend(v)) <= 100) {
		vector<set<int>> pp(101);
		for (int i = 0;i < n;i++) pp[a[i]].insert(i);
		for (int i = 0;i < q;i++) {
			pp[a[x[i]]].erase(x[i]);
			pp[a[x[i]] = v[i]].insert(x[i]);
			for (int j = 1, cnt = 0;j < 101;j++) {
				
				if (!pp[j].empty()) {
					ans[i] = max(ans[i],*pp[j].rbegin() - (cnt += sz(pp[j])) + 1);
				}
			} 
		}
		return ans;
	}
}

// signed main() {
    // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // if (ifstream(NAME".inp")) {
        // freopen(NAME".inp","r",stdin);
        // freopen(NAME".out","w",stdout);
    // }
    // vector<int> a = {1, 2, 3, 4};
    // vector<int> x = {0, 2};
    // vector<int> v = {3, 1};
    // vector<int> ans = countScans(a, x, v);
    // for (auto x : ans) cout << x << '\n';
//     
//     
    // cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    // return 0;
// }
// agent pengin wants to take apio (with anya-san)

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:74:1: warning: control reaches end of non-void function [-Wreturn-type]
   74 | }
      | ^

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 0 / 40