oj.uz

Submission #270463

# Submission time Handle Problem Language Result Execution time Memory
270463 2020-08-17T16:10:48 Z limabeans Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 2524 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 brute(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;
}

int solve(vector<int> a) {
    vector<int> sa = a;
    int n = a.size();
    sort(sa.begin(), sa.end());
    map<int,vector<int>> inds;
    for (int i=n-1; i>=0; i--) {
	inds[sa[i]].push_back(i);
    }
    int mx = 0;

    for (int i=0; i<n; i++) {
	int to = inds[a[i]].back();
	if (to < i) {
	    mx = max(mx, i-to);
	}
	inds[a[i]].pop_back();
    }

    return mx;
}


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);
	//cout<<solve(A)<<" ans: "<<brute(A)<<endl;
	//assert(brute(A) == solve(A));

	res[i] = solve(A);
    }

    return res;
}


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

    //out(brute({7, 4, 6, 3, 1, 3, 1, 8, 9, 8 }));

    int n,q;
    cin>>n>>q;
    vector<int> a(n);
    for (int i=0; i<n; i++) {
	cin>>a[i];
    }
    vector<int> x, v;
    while (q--) {
	int i, val;
	cin>>i>>val;
	x.push_back(i);
	v.push_back(val);
    }

    auto res = countScans(a,x,v);
    for (int i: res) cout<<i<<" ";
    cout<<endl;
    
    
    return 0;
}
*/

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 384 KB Output is correct
2 Correct 251 ms 384 KB Output is correct
3 Correct 1600 ms 656 KB Output is correct
4 Correct 1586 ms 760 KB Output is correct
5 Correct 1531 ms 640 KB Output is correct
6 Correct 1257 ms 640 KB Output is correct
7 Correct 1423 ms 700 KB Output is correct
8 Correct 1517 ms 692 KB Output is correct
9 Correct 1620 ms 692 KB Output is correct
10 Correct 1289 ms 692 KB Output is correct
11 Correct 1282 ms 760 KB Output is correct
12 Correct 1294 ms 640 KB Output is correct
13 Correct 1356 ms 760 KB Output is correct
14 Correct 1293 ms 688 KB Output is correct
15 Correct 1304 ms 760 KB Output is correct
16 Correct 1334 ms 760 KB Output is correct
17 Correct 1266 ms 684 KB Output is correct
18 Correct 1299 ms 684 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 384 KB Output is correct
2 Correct 251 ms 384 KB Output is correct
3 Correct 1600 ms 656 KB Output is correct
4 Correct 1586 ms 760 KB Output is correct
5 Correct 1531 ms 640 KB Output is correct
6 Correct 1257 ms 640 KB Output is correct
7 Correct 1423 ms 700 KB Output is correct
8 Correct 1517 ms 692 KB Output is correct
9 Correct 1620 ms 692 KB Output is correct
10 Correct 1289 ms 692 KB Output is correct
11 Correct 1282 ms 760 KB Output is correct
12 Correct 1294 ms 640 KB Output is correct
13 Correct 1356 ms 760 KB Output is correct
14 Correct 1293 ms 688 KB Output is correct
15 Correct 1304 ms 760 KB Output is correct
16 Correct 1334 ms 760 KB Output is correct
17 Correct 1266 ms 684 KB Output is correct
18 Correct 1299 ms 684 KB Output is correct
19 Execution timed out 9072 ms 1536 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8163 ms 1644 KB Output is correct
2 Execution timed out 9021 ms 2524 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 384 KB Output is correct
2 Correct 251 ms 384 KB Output is correct
3 Correct 1600 ms 656 KB Output is correct
4 Correct 1586 ms 760 KB Output is correct
5 Correct 1531 ms 640 KB Output is correct
6 Correct 1257 ms 640 KB Output is correct
7 Correct 1423 ms 700 KB Output is correct
8 Correct 1517 ms 692 KB Output is correct
9 Correct 1620 ms 692 KB Output is correct
10 Correct 1289 ms 692 KB Output is correct
11 Correct 1282 ms 760 KB Output is correct
12 Correct 1294 ms 640 KB Output is correct
13 Correct 1356 ms 760 KB Output is correct
14 Correct 1293 ms 688 KB Output is correct
15 Correct 1304 ms 760 KB Output is correct
16 Correct 1334 ms 760 KB Output is correct
17 Correct 1266 ms 684 KB Output is correct
18 Correct 1299 ms 684 KB Output is correct
19 Execution timed out 9072 ms 1536 KB Time limit exceeded
20 Halted 0 ms 0 KB -