oj.uz

Submission #270454

# Submission time Handle Problem Language Result Execution time Memory
270454 2020-08-17T15:51:12 Z limabeans Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
 9000 ms 832 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 376 KB Output is correct
2 Correct 1342 ms 408 KB Output is correct
3 Execution timed out 9068 ms 384 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 376 KB Output is correct
2 Correct 1342 ms 408 KB Output is correct
3 Execution timed out 9068 ms 384 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9073 ms 832 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 376 KB Output is correct
2 Correct 1342 ms 408 KB Output is correct
3 Execution timed out 9068 ms 384 KB Time limit exceeded
4 Halted 0 ms 0 KB -