oj.uz

Submission #1012084

# Submission time Handle Problem Language Result Execution time Memory
1012084 2024-07-01T15:38:46 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
38 / 100
 9000 ms 2476 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sort undefined_function // To use stable_sort instead sort 
#define bpc __builtin_popcount
#define ull unsigned long long
#define ld double
#define ll long long
#define mp make_pair
#define F first
#define S second

#pragma GCC optimize("O3")

#ifdef LOCAL 
	#include "debug.h"
#else 
	#define dbg(...) 0
#endif

using namespace __gnu_pbds;
using namespace std;

typedef tree<long long, null_type, less_equal<long long>,
    rb_tree_tag, tree_order_statistics_node_update> Tree;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll INF = 9223372036854775807LL;
const ll inf = 2147483647;
const ll MOD = 998244353; //[998244353, 1e9 + 7, 1e9 + 13]
const ld PI = acos(-1);
const ll NROOT = 800;

ll binpow(ll a, ll b, ll _MOD = -1) {
	if (_MOD == -1)
		_MOD = MOD;
	ll res = 1;
	for (; b; b /= 2, a *= a, a %= _MOD)
		if (b & 1) res *= a, res %= _MOD;
	return res;
}

void set_IO(string s) {
#ifndef LOCAL
	string in  = s +  ".in";
	string out = s + ".out";
	freopen(in.c_str(),  "r",  stdin);
	freopen(out.c_str(), "w", stdout);
#endif
}

bool dataOverflow(ll a, ll b) {return (log10(a) + log10(b) >= 18);}
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a * b / gcd(a, b);}
ll ceil(ll a, ll b) {return (a + b - 1) / b;}
ll invmod(ll a) {return binpow(a, MOD - 2);}

int FindBrute(vector<int> v) {
	int cnt = 0;
	//dbg(">>>", v);
	for (int i = 0; i < (int)v.size(); i ++) {
		if (is_sorted(v.begin(), v.end()))
			break;
		cnt ++;
		for (int j = 0; j < (int)v.size() - 1; j ++) {
			if (v[j] > v[j + 1])
				swap(v[j], v[j + 1]);
		}
	//	dbg(v);
	}

	return cnt;
}

class FT{
	private:
		int n;
		vector<int> v;

	public:
		FT(int _n) {
			n = _n;
			v.resize(n + 1);
		}

		void update(int p, int x) {
			while (p <= n) {
				v[p] += x;
				p += p & -p;
			}
		}

		int query(int p) {
			int ans = 0;
			while (0 < p) {
				ans += v[p];
				p -= p & -p;
			}
			return ans;
		}

		int revQuery(int p) {
			return query(n) - query(p - 1);
		}
};

int FindSmart(vector<int> v) {
	FT f(*max_element(v.begin(), v.end()) + 10); 
	int mx = 0;
	for (int i = 0; i < v.size(); i ++) {
		mx = max(mx, f.revQuery(v[i] + 1));
		f.update(v[i], 1);
	}
	return mx;
}

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

	for (auto &x : A)
		s.insert(x);
	for (auto &x : V)
		s.insert(x);

	int index = 0;
	map<int, int> ID;

	for (auto &x : s)
		ID[x] = ++index;
	vector<int> res;

	for (auto &x : A)
		x = ID[x];

	for (int i = 0; i < (int)V.size(); i ++) {
		A[X[i]] = ID[V[i]];
		res.push_back(FindSmart(A));
	}

	return res;
}

Compilation message

bubblesort2.cpp: In function 'int FindSmart(std::vector<int>)':
bubblesort2.cpp:110:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |  for (int i = 0; i < v.size(); i ++) {
      |                  ~~^~~~~~~~~~
bubblesort2.cpp: In function 'void set_IO(std::string)':
bubblesort2.cpp:47:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  freopen(in.c_str(),  "r",  stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bubblesort2.cpp:48:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  freopen(out.c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 11 ms 628 KB Output is correct
3 Correct 73 ms 860 KB Output is correct
4 Correct 74 ms 876 KB Output is correct
5 Correct 72 ms 856 KB Output is correct
6 Correct 70 ms 856 KB Output is correct
7 Correct 71 ms 876 KB Output is correct
8 Correct 72 ms 868 KB Output is correct
9 Correct 72 ms 860 KB Output is correct
10 Correct 63 ms 832 KB Output is correct
11 Correct 65 ms 600 KB Output is correct
12 Correct 69 ms 604 KB Output is correct
13 Correct 70 ms 812 KB Output is correct
14 Correct 57 ms 1056 KB Output is correct
15 Correct 62 ms 600 KB Output is correct
16 Correct 59 ms 784 KB Output is correct
17 Correct 59 ms 604 KB Output is correct
18 Correct 62 ms 792 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 11 ms 628 KB Output is correct
3 Correct 73 ms 860 KB Output is correct
4 Correct 74 ms 876 KB Output is correct
5 Correct 72 ms 856 KB Output is correct
6 Correct 70 ms 856 KB Output is correct
7 Correct 71 ms 876 KB Output is correct
8 Correct 72 ms 868 KB Output is correct
9 Correct 72 ms 860 KB Output is correct
10 Correct 63 ms 832 KB Output is correct
11 Correct 65 ms 600 KB Output is correct
12 Correct 69 ms 604 KB Output is correct
13 Correct 70 ms 812 KB Output is correct
14 Correct 57 ms 1056 KB Output is correct
15 Correct 62 ms 600 KB Output is correct
16 Correct 59 ms 784 KB Output is correct
17 Correct 59 ms 604 KB Output is correct
18 Correct 62 ms 792 KB Output is correct
19 Correct 1171 ms 1884 KB Output is correct
20 Correct 1408 ms 2140 KB Output is correct
21 Correct 1335 ms 2216 KB Output is correct
22 Correct 1380 ms 2476 KB Output is correct
23 Correct 1245 ms 2032 KB Output is correct
24 Correct 1224 ms 1880 KB Output is correct
25 Correct 1161 ms 2176 KB Output is correct
26 Correct 1138 ms 1880 KB Output is correct
27 Correct 1192 ms 2080 KB Output is correct
28 Correct 1213 ms 1872 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 901 ms 600 KB Output is correct
2 Execution timed out 9024 ms 1644 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 11 ms 628 KB Output is correct
3 Correct 73 ms 860 KB Output is correct
4 Correct 74 ms 876 KB Output is correct
5 Correct 72 ms 856 KB Output is correct
6 Correct 70 ms 856 KB Output is correct
7 Correct 71 ms 876 KB Output is correct
8 Correct 72 ms 868 KB Output is correct
9 Correct 72 ms 860 KB Output is correct
10 Correct 63 ms 832 KB Output is correct
11 Correct 65 ms 600 KB Output is correct
12 Correct 69 ms 604 KB Output is correct
13 Correct 70 ms 812 KB Output is correct
14 Correct 57 ms 1056 KB Output is correct
15 Correct 62 ms 600 KB Output is correct
16 Correct 59 ms 784 KB Output is correct
17 Correct 59 ms 604 KB Output is correct
18 Correct 62 ms 792 KB Output is correct
19 Correct 1171 ms 1884 KB Output is correct
20 Correct 1408 ms 2140 KB Output is correct
21 Correct 1335 ms 2216 KB Output is correct
22 Correct 1380 ms 2476 KB Output is correct
23 Correct 1245 ms 2032 KB Output is correct
24 Correct 1224 ms 1880 KB Output is correct
25 Correct 1161 ms 2176 KB Output is correct
26 Correct 1138 ms 1880 KB Output is correct
27 Correct 1192 ms 2080 KB Output is correct
28 Correct 1213 ms 1872 KB Output is correct
29 Correct 901 ms 600 KB Output is correct
30 Execution timed out 9024 ms 1644 KB Time limit exceeded
31 Halted 0 ms 0 KB -