Submission #270454

#	Time	Username	Problem	Language	Result	Execution time	Memory
270454		limabeans	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	9073 ms	832 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;



bool sorted(vector<int> a) {
    int n = a.size();
    for (int i=1; i<n; i++) {
	if (a[i] < a[i-1]) return false;
    }
    return true;
}

int solve(vector<int> a) {
    int n = a.size();
    int res = 0;
    while (!sorted(a)) {
	res++;
	for (int i=0; i<n-1; i++) {
	    if (a[i] > a[i+1]) swap(a[i], a[i+1]);
	}
    }
    return res;
}


void print(vector<int> a) {
    for (int i: a) cout<<i<<" ";
    cout<<endl;
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
    int Q = X.size();
    vector<int> res(Q);
    for (int i=0; i<Q; i++) {
	A[X[i]] = V[i];
	//print(A);
	res[i] = solve(A);
    }

    return res;
}


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

    auto res = countScans({1,2,3,4}, {0,2}, {3,1});
    for (int x: res) cout<<x<<" ";
    cout<<endl;
    
    
    return 0;
}
*/

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