oj.uz

Submission #270490

# Submission time Handle Problem Language Result Execution time Memory
270490 2020-08-17T16:33:49 Z limabeans Bubble Sort 2 (JOI18_bubblesort2) C++17
39 / 100
 9000 ms 5656 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> solveTask3(vector<int> A, vector<int> X, vector<int> V) {
    //cerr<<"task3"<<endl;
    
    int n = A.size();
    vector<set<int>> inds(102);
    for (int i=0; i<n; i++) {
	inds[A[i]].insert(i);
    }

    vector<int> ans;

    for (int q=0; q<(int)X.size(); q++) {
	int idx = X[q];
	int val = V[q];
	inds[A[idx]].erase(idx);
	A[idx] = val;
	inds[A[idx]].insert(idx);

	int mx = 0;
	int prev = 0;
	for (int i=1; i<=100; i++) {
	    if (inds[i].empty()) {
		continue;
	    }
	    int dest = prev + int(inds[i].size()) - 1;
	    int dist = *inds[i].rbegin() - dest;
	    mx = max(mx, dist);
	    prev += int(inds[i].size());
	}
	//assert(mx == brute(A));
	ans.push_back(mx);
    }

    return ans;
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
    if (max(*max_element(A.begin(),A.end()), *max_element(V.begin(),V.end())) <= 100) {
	return solveTask3(A,X,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 98 ms 384 KB Output is correct
2 Correct 242 ms 504 KB Output is correct
3 Correct 1535 ms 652 KB Output is correct
4 Correct 1536 ms 648 KB Output is correct
5 Correct 1493 ms 760 KB Output is correct
6 Correct 1210 ms 760 KB Output is correct
7 Correct 1325 ms 768 KB Output is correct
8 Correct 1439 ms 652 KB Output is correct
9 Correct 1501 ms 648 KB Output is correct
10 Correct 1270 ms 760 KB Output is correct
11 Correct 1278 ms 760 KB Output is correct
12 Correct 1269 ms 736 KB Output is correct
13 Correct 1279 ms 644 KB Output is correct
14 Correct 1259 ms 652 KB Output is correct
15 Correct 1255 ms 760 KB Output is correct
16 Correct 1262 ms 792 KB Output is correct
17 Correct 1294 ms 760 KB Output is correct
18 Correct 1254 ms 644 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 384 KB Output is correct
2 Correct 242 ms 504 KB Output is correct
3 Correct 1535 ms 652 KB Output is correct
4 Correct 1536 ms 648 KB Output is correct
5 Correct 1493 ms 760 KB Output is correct
6 Correct 1210 ms 760 KB Output is correct
7 Correct 1325 ms 768 KB Output is correct
8 Correct 1439 ms 652 KB Output is correct
9 Correct 1501 ms 648 KB Output is correct
10 Correct 1270 ms 760 KB Output is correct
11 Correct 1278 ms 760 KB Output is correct
12 Correct 1269 ms 736 KB Output is correct
13 Correct 1279 ms 644 KB Output is correct
14 Correct 1259 ms 652 KB Output is correct
15 Correct 1255 ms 760 KB Output is correct
16 Correct 1262 ms 792 KB Output is correct
17 Correct 1294 ms 760 KB Output is correct
18 Correct 1254 ms 644 KB Output is correct
19 Execution timed out 9085 ms 1280 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2048 KB Output is correct
2 Correct 46 ms 3448 KB Output is correct
3 Correct 86 ms 5368 KB Output is correct
4 Correct 86 ms 5368 KB Output is correct
5 Correct 87 ms 5368 KB Output is correct
6 Correct 86 ms 5368 KB Output is correct
7 Correct 90 ms 5368 KB Output is correct
8 Correct 86 ms 5368 KB Output is correct
9 Correct 86 ms 5496 KB Output is correct
10 Correct 73 ms 5496 KB Output is correct
11 Correct 72 ms 5496 KB Output is correct
12 Correct 78 ms 5496 KB Output is correct
13 Correct 70 ms 5656 KB Output is correct
14 Correct 73 ms 5496 KB Output is correct
15 Correct 67 ms 5500 KB Output is correct
16 Correct 63 ms 5624 KB Output is correct
17 Correct 61 ms 5496 KB Output is correct
18 Correct 61 ms 5496 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 384 KB Output is correct
2 Correct 242 ms 504 KB Output is correct
3 Correct 1535 ms 652 KB Output is correct
4 Correct 1536 ms 648 KB Output is correct
5 Correct 1493 ms 760 KB Output is correct
6 Correct 1210 ms 760 KB Output is correct
7 Correct 1325 ms 768 KB Output is correct
8 Correct 1439 ms 652 KB Output is correct
9 Correct 1501 ms 648 KB Output is correct
10 Correct 1270 ms 760 KB Output is correct
11 Correct 1278 ms 760 KB Output is correct
12 Correct 1269 ms 736 KB Output is correct
13 Correct 1279 ms 644 KB Output is correct
14 Correct 1259 ms 652 KB Output is correct
15 Correct 1255 ms 760 KB Output is correct
16 Correct 1262 ms 792 KB Output is correct
17 Correct 1294 ms 760 KB Output is correct
18 Correct 1254 ms 644 KB Output is correct
19 Execution timed out 9085 ms 1280 KB Time limit exceeded
20 Halted 0 ms 0 KB -