oj.uz

Submission #649487

# Submission time Handle Problem Language Result Execution time Memory
649487 2022-10-10T09:52:29 Z BackNoob Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 9000 ms 724 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()

using namespace std;
const int mxN = 5e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

vector<int> countScans(vector<int> a, vector<int> q1, vector<int> q2)
{
    vector<int> ans;
    for(int i = 0; i < sz(q1); i++) {
        int pos = q1[i];
        int val = q2[i];
        a[pos] = val;
        int cur = inf;
        int res = 0;
        vector<int> fin = a;
        vector<int> tmp = a;
        sort(all(fin));
        while(tmp != fin) {
            for(int i = 0; i + 1 < sz(tmp); i++) {
                if(tmp[i] > tmp[i + 1]) {
                    swap(tmp[i], tmp[i + 1]);
                }
            }
            ++res;
        }
        ans.pb(res);
    }
    return ans;
}

//void solve()
//{
//    vector<int> a;
//    vector<int> q1;
//    vector<int> q2;
//    int n;
//    cin >> n;
//    for(int i = 1; i <= n; i++) {
//        int x;
//        cin >> x;
//        a.pb(x);
//    }
//
//
//    int q;
//    cin >> q;
//    for(int i = 1; i <= q; i++) {
//        int p, v;
//        cin >> p >> v;
//        q1.pb(p);
//        q2.pb(v);
//    }
//    vector<int> res = countScans(a, q1, q2);
//    for(auto it : res) cout << it << endl;
//}
//
//int main()
//{
//    ios_base::sync_with_stdio(0);
//    cin.tie(0);
//    freopen(TASK".inp" , "r" , stdin);
//    freopen(TASK".out" , "w" , stdout);
//
//    int tc = 1;
//    //cin >> tc;
//    while(tc--) {
//    	solve();
//    }
//    return 0;
//}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:38:13: warning: unused variable 'cur' [-Wunused-variable]
   38 |         int cur = inf;
      |             ^~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 300 KB Output is correct
2 Correct 895 ms 452 KB Output is correct
3 Execution timed out 9012 ms 464 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 300 KB Output is correct
2 Correct 895 ms 452 KB Output is correct
3 Execution timed out 9012 ms 464 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9090 ms 724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 300 KB Output is correct
2 Correct 895 ms 452 KB Output is correct
3 Execution timed out 9012 ms 464 KB Time limit exceeded
4 Halted 0 ms 0 KB -