oj.uz

Submission #70973

# Submission time Handle Problem Language Result Execution time Memory
70973 2018-08-23T22:56:14 Z dmfr Bubble Sort 2 (JOI18_bubblesort2) C++11
38 / 100
 9000 ms 6444 KB 
#include "bubblesort2.h"
#include <set>
#include <algorithm>

//#include <iostream>

using namespace std;

class Number{
public:
    int Val;
    int OriginalPos;
    Number(){}
    Number(const int& Val_, const int& OriginalPos_): Val(Val_), OriginalPos(OriginalPos_){}
    bool operator<(const Number& obj)const{
        if(this->Val != obj.Val) return (this->Val < obj.Val);
        else                     return (this->OriginalPos < obj.OriginalPos);
    }
};

int solve(const set<Number>& NumberSet, vector<int>& dif){
    const int& N = dif.size();

    set<Number>::iterator it = NumberSet.begin();
    for(int i = 0; i < N; ++i, ++it)
        dif[i] = i - it->OriginalPos;

    int ret = *min_element(dif.begin(), dif.end());
    return -ret;
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){

/*
4 2
1 2 3 4
0 3
2 1
=>1
=>2
*/

	const int& N = A.size();
	const int& Q = X.size();

	vector<Number> NumberVtr(N);
	for(int i = 0; i < N; ++i)
        NumberVtr[i] = Number(A[i], i);
	set<Number> NumberSet(NumberVtr.begin(), NumberVtr.end());

	vector<int> answer(Q);

	vector<int> dif(N);

    for(int i = 0; i < Q; ++i){
        const int& index_NumberToChange = X[i];
        Number& NumberToChange = NumberVtr[index_NumberToChange];
        NumberSet.erase(NumberSet.find(NumberToChange));
        NumberToChange.Val = V[i];
        NumberSet.insert(NumberToChange);
        answer[i] = solve(NumberSet, dif);
    }

//    cout << "answer: ";
//    for(int i = 0; i < Q; ++i)
//        cout << answer[i] << " ";
//    cout << endl;


	return answer;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 11 ms 492 KB Output is correct
3 Correct 59 ms 716 KB Output is correct
4 Correct 58 ms 824 KB Output is correct
5 Correct 52 ms 824 KB Output is correct
6 Correct 46 ms 868 KB Output is correct
7 Correct 49 ms 1040 KB Output is correct
8 Correct 49 ms 1040 KB Output is correct
9 Correct 58 ms 1216 KB Output is correct
10 Correct 51 ms 1216 KB Output is correct
11 Correct 43 ms 1304 KB Output is correct
12 Correct 50 ms 1304 KB Output is correct
13 Correct 43 ms 1388 KB Output is correct
14 Correct 49 ms 1388 KB Output is correct
15 Correct 46 ms 1388 KB Output is correct
16 Correct 46 ms 1388 KB Output is correct
17 Correct 50 ms 1496 KB Output is correct
18 Correct 45 ms 1496 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 11 ms 492 KB Output is correct
3 Correct 59 ms 716 KB Output is correct
4 Correct 58 ms 824 KB Output is correct
5 Correct 52 ms 824 KB Output is correct
6 Correct 46 ms 868 KB Output is correct
7 Correct 49 ms 1040 KB Output is correct
8 Correct 49 ms 1040 KB Output is correct
9 Correct 58 ms 1216 KB Output is correct
10 Correct 51 ms 1216 KB Output is correct
11 Correct 43 ms 1304 KB Output is correct
12 Correct 50 ms 1304 KB Output is correct
13 Correct 43 ms 1388 KB Output is correct
14 Correct 49 ms 1388 KB Output is correct
15 Correct 46 ms 1388 KB Output is correct
16 Correct 46 ms 1388 KB Output is correct
17 Correct 50 ms 1496 KB Output is correct
18 Correct 45 ms 1496 KB Output is correct
19 Correct 1170 ms 2136 KB Output is correct
20 Correct 1614 ms 2444 KB Output is correct
21 Correct 1088 ms 2644 KB Output is correct
22 Correct 1290 ms 2840 KB Output is correct
23 Correct 1076 ms 2908 KB Output is correct
24 Correct 1099 ms 3200 KB Output is correct
25 Correct 1112 ms 3308 KB Output is correct
26 Correct 1165 ms 3412 KB Output is correct
27 Correct 1139 ms 3700 KB Output is correct
28 Correct 1106 ms 3772 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1750 ms 4908 KB Output is correct
2 Execution timed out 9035 ms 6444 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 11 ms 492 KB Output is correct
3 Correct 59 ms 716 KB Output is correct
4 Correct 58 ms 824 KB Output is correct
5 Correct 52 ms 824 KB Output is correct
6 Correct 46 ms 868 KB Output is correct
7 Correct 49 ms 1040 KB Output is correct
8 Correct 49 ms 1040 KB Output is correct
9 Correct 58 ms 1216 KB Output is correct
10 Correct 51 ms 1216 KB Output is correct
11 Correct 43 ms 1304 KB Output is correct
12 Correct 50 ms 1304 KB Output is correct
13 Correct 43 ms 1388 KB Output is correct
14 Correct 49 ms 1388 KB Output is correct
15 Correct 46 ms 1388 KB Output is correct
16 Correct 46 ms 1388 KB Output is correct
17 Correct 50 ms 1496 KB Output is correct
18 Correct 45 ms 1496 KB Output is correct
19 Correct 1170 ms 2136 KB Output is correct
20 Correct 1614 ms 2444 KB Output is correct
21 Correct 1088 ms 2644 KB Output is correct
22 Correct 1290 ms 2840 KB Output is correct
23 Correct 1076 ms 2908 KB Output is correct
24 Correct 1099 ms 3200 KB Output is correct
25 Correct 1112 ms 3308 KB Output is correct
26 Correct 1165 ms 3412 KB Output is correct
27 Correct 1139 ms 3700 KB Output is correct
28 Correct 1106 ms 3772 KB Output is correct
29 Correct 1750 ms 4908 KB Output is correct
30 Execution timed out 9035 ms 6444 KB Time limit exceeded
31 Halted 0 ms 0 KB -