Submission #224812

#	Time	Username	Problem	Language	Result	Execution time	Memory
224812		Bruteforceman	Bubble Sort 2 (JOI18_bubblesort2)	C++11	38 / 100	9017 ms	2428 KiB

bubblesort2

#include "bits/stdc++.h"
#include "bubblesort2.h"
using namespace std;

int solve(vector <int> &A) {
    vector <int> cmp (A.size()), pos (A.size());
    for(int i = 0; i < A.size(); i++) cmp[i] = i;
    stable_sort(cmp.begin(), cmp.end(), [&] (int i, int j) { return A[i] < A[j]; });
    for(int i = 0; i < A.size(); i++) pos[cmp[i]] = i;
    int ans = 0;
    for(int i = 0; i < A.size(); i++) {
        ans = max(ans, i - pos[i]);
    }
    return ans;
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
    vector <int> answer (X.size());
    for(int i = 0; i < X.size(); i++) {
        A[X[i]] = V[i];
        answer[i] = solve(A);
    }
	return answer;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'int solve(std::vector<int>&)':
bubblesort2.cpp:7:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < A.size(); i++) cmp[i] = i;
                    ~~^~~~~~~~~~
bubblesort2.cpp:9:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < A.size(); i++) pos[cmp[i]] = i;
                    ~~^~~~~~~~~~
bubblesort2.cpp:11:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < A.size(); i++) {
                    ~~^~~~~~~~~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:19:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < X.size(); i++) {
                    ~~^~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40