답안 #70975 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70975	2018-08-23T23:00:20 Z	dmfr	Bubble Sort 2 (JOI18_bubblesort2)	C++11	38 / 100	9000 ms	6640 KB

bubblesort2

#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();

    int min_ = 0;

    set<Number>::iterator it = NumberSet.begin();
    for(int i = 0; i < N; ++i, ++it){
        min_ = min(min_, i - it->OriginalPos);
        if(i - (N-1) > min_) break;
    }

    return -min_;
}

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

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	484 KB	Output is correct
3	Correct	6 ms	680 KB	Output is correct
4	Correct	5 ms	680 KB	Output is correct
5	Correct	28 ms	700 KB	Output is correct
6	Correct	35 ms	700 KB	Output is correct
7	Correct	35 ms	752 KB	Output is correct
8	Correct	35 ms	864 KB	Output is correct
9	Correct	30 ms	864 KB	Output is correct
10	Correct	19 ms	864 KB	Output is correct
11	Correct	19 ms	864 KB	Output is correct
12	Correct	19 ms	864 KB	Output is correct
13	Correct	18 ms	864 KB	Output is correct
14	Correct	19 ms	864 KB	Output is correct
15	Correct	19 ms	864 KB	Output is correct
16	Correct	19 ms	864 KB	Output is correct
17	Correct	18 ms	864 KB	Output is correct
18	Correct	18 ms	864 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	484 KB	Output is correct
3	Correct	6 ms	680 KB	Output is correct
4	Correct	5 ms	680 KB	Output is correct
5	Correct	28 ms	700 KB	Output is correct
6	Correct	35 ms	700 KB	Output is correct
7	Correct	35 ms	752 KB	Output is correct
8	Correct	35 ms	864 KB	Output is correct
9	Correct	30 ms	864 KB	Output is correct
10	Correct	19 ms	864 KB	Output is correct
11	Correct	19 ms	864 KB	Output is correct
12	Correct	19 ms	864 KB	Output is correct
13	Correct	18 ms	864 KB	Output is correct
14	Correct	19 ms	864 KB	Output is correct
15	Correct	19 ms	864 KB	Output is correct
16	Correct	19 ms	864 KB	Output is correct
17	Correct	18 ms	864 KB	Output is correct
18	Correct	18 ms	864 KB	Output is correct
19	Correct	22 ms	1164 KB	Output is correct
20	Correct	20 ms	1292 KB	Output is correct
21	Correct	823 ms	1316 KB	Output is correct
22	Correct	787 ms	1420 KB	Output is correct
23	Correct	280 ms	1420 KB	Output is correct
24	Correct	303 ms	1420 KB	Output is correct
25	Correct	315 ms	1420 KB	Output is correct
26	Correct	294 ms	1420 KB	Output is correct
27	Correct	325 ms	1524 KB	Output is correct
28	Correct	328 ms	1524 KB	Output is correct

Subtask #3
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	2452 KB	Output is correct
2	Correct	193 ms	3860 KB	Output is correct
3	Correct	530 ms	5540 KB	Output is correct
4	Correct	519 ms	6080 KB	Output is correct
5	Execution timed out	9073 ms	6640 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #4
0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	484 KB	Output is correct
3	Correct	6 ms	680 KB	Output is correct
4	Correct	5 ms	680 KB	Output is correct
5	Correct	28 ms	700 KB	Output is correct
6	Correct	35 ms	700 KB	Output is correct
7	Correct	35 ms	752 KB	Output is correct
8	Correct	35 ms	864 KB	Output is correct
9	Correct	30 ms	864 KB	Output is correct
10	Correct	19 ms	864 KB	Output is correct
11	Correct	19 ms	864 KB	Output is correct
12	Correct	19 ms	864 KB	Output is correct
13	Correct	18 ms	864 KB	Output is correct
14	Correct	19 ms	864 KB	Output is correct
15	Correct	19 ms	864 KB	Output is correct
16	Correct	19 ms	864 KB	Output is correct
17	Correct	18 ms	864 KB	Output is correct
18	Correct	18 ms	864 KB	Output is correct
19	Correct	22 ms	1164 KB	Output is correct
20	Correct	20 ms	1292 KB	Output is correct
21	Correct	823 ms	1316 KB	Output is correct
22	Correct	787 ms	1420 KB	Output is correct
23	Correct	280 ms	1420 KB	Output is correct
24	Correct	303 ms	1420 KB	Output is correct
25	Correct	315 ms	1420 KB	Output is correct
26	Correct	294 ms	1420 KB	Output is correct
27	Correct	325 ms	1524 KB	Output is correct
28	Correct	328 ms	1524 KB	Output is correct
29	Correct	26 ms	2452 KB	Output is correct
30	Correct	193 ms	3860 KB	Output is correct
31	Correct	530 ms	5540 KB	Output is correct
32	Correct	519 ms	6080 KB	Output is correct
33	Execution timed out	9073 ms	6640 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

답안 #70975

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 21.0 / 21.0

Subtask #3 0 / 22.0

Subtask #4 0 / 40.0

Subtask #1
17.0 / 17.0

Subtask #2
21.0 / 21.0

Subtask #3
0 / 22.0

Subtask #4
0 / 40.0