oj.uz

Submission #430291

# Submission time Handle Problem Language Result Execution time Memory
430291 2021-06-16T12:42:21 Z vulpes2 Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 1228 KB 
#include <iostream>
#include <map>
#include <list>
#include <set>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <iterator>
#include <random>
#include <chrono>
#include <complex>
#include <bitset>
#include <fstream>
 
 
#define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
#define set_map_includes(set, elt) (set.find((elt)) != set.end())
#define readint(i) int i; cin >> i
#define readll(i) ll i; cin >> i
#define readdouble(i) double i; cin >> i
#define readstring(s) string s; cin >> s

typedef long long ll;

 
//using namespace __gnu_pbds;
//using namespace atcoder;
using namespace std;

const ll modd = (1000LL * 1000LL * 1000LL + 7LL);
//const ll modd = 998244353;

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
    map<int,int> dict;
    for(auto x : A) {  dict[x] = 0;   }
    for(auto x : V) {  dict[x] = 0;   }
    int i = 0;
    for(auto it = dict.begin(); it != dict.end(); ++it) {
        it->second = i; ++i;
    }
    for(auto& x : A) { x = dict[x]; }
    for(auto& x : V) { x = dict[x]; }

	int Q=X.size();
	std::vector<int> answer(Q);
	for (int j=0;j<Q;j++) {
        A[X[j]] = V[j];
        int ans = 0;
        vector<int> a_copy(A.begin(), A.end());
        sort(a_copy.begin(), a_copy.end());
        forr(i,0,A.size()) {
            int k = upper_bound(a_copy.begin(), a_copy.end(), A[i]) - a_copy.begin();
            --k;
            ans = max(ans, i-k);
        }
		answer[j]=ans;
	}
	return answer;
}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:23:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 | #define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
      |                                                     ^
bubblesort2.cpp:58:9: note: in expansion of macro 'forr'
   58 |         forr(i,0,A.size()) {
      |         ^~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 332 KB Output is correct
2 Correct 87 ms 332 KB Output is correct
3 Correct 524 ms 524 KB Output is correct
4 Correct 510 ms 460 KB Output is correct
5 Correct 491 ms 520 KB Output is correct
6 Correct 327 ms 516 KB Output is correct
7 Correct 402 ms 528 KB Output is correct
8 Correct 449 ms 520 KB Output is correct
9 Correct 476 ms 520 KB Output is correct
10 Correct 343 ms 488 KB Output is correct
11 Correct 332 ms 504 KB Output is correct
12 Correct 349 ms 492 KB Output is correct
13 Correct 329 ms 484 KB Output is correct
14 Correct 332 ms 484 KB Output is correct
15 Correct 331 ms 480 KB Output is correct
16 Correct 321 ms 472 KB Output is correct
17 Correct 322 ms 476 KB Output is correct
18 Correct 361 ms 472 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 332 KB Output is correct
2 Correct 87 ms 332 KB Output is correct
3 Correct 524 ms 524 KB Output is correct
4 Correct 510 ms 460 KB Output is correct
5 Correct 491 ms 520 KB Output is correct
6 Correct 327 ms 516 KB Output is correct
7 Correct 402 ms 528 KB Output is correct
8 Correct 449 ms 520 KB Output is correct
9 Correct 476 ms 520 KB Output is correct
10 Correct 343 ms 488 KB Output is correct
11 Correct 332 ms 504 KB Output is correct
12 Correct 349 ms 492 KB Output is correct
13 Correct 329 ms 484 KB Output is correct
14 Correct 332 ms 484 KB Output is correct
15 Correct 331 ms 480 KB Output is correct
16 Correct 321 ms 472 KB Output is correct
17 Correct 322 ms 476 KB Output is correct
18 Correct 361 ms 472 KB Output is correct
19 Correct 7904 ms 1144 KB Output is correct
20 Execution timed out 9083 ms 1228 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7719 ms 636 KB Output is correct
2 Execution timed out 9032 ms 1228 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 332 KB Output is correct
2 Correct 87 ms 332 KB Output is correct
3 Correct 524 ms 524 KB Output is correct
4 Correct 510 ms 460 KB Output is correct
5 Correct 491 ms 520 KB Output is correct
6 Correct 327 ms 516 KB Output is correct
7 Correct 402 ms 528 KB Output is correct
8 Correct 449 ms 520 KB Output is correct
9 Correct 476 ms 520 KB Output is correct
10 Correct 343 ms 488 KB Output is correct
11 Correct 332 ms 504 KB Output is correct
12 Correct 349 ms 492 KB Output is correct
13 Correct 329 ms 484 KB Output is correct
14 Correct 332 ms 484 KB Output is correct
15 Correct 331 ms 480 KB Output is correct
16 Correct 321 ms 472 KB Output is correct
17 Correct 322 ms 476 KB Output is correct
18 Correct 361 ms 472 KB Output is correct
19 Correct 7904 ms 1144 KB Output is correct
20 Execution timed out 9083 ms 1228 KB Time limit exceeded
21 Halted 0 ms 0 KB -