oj.uz

Submission #1012061

# Submission time Handle Problem Language Result Execution time Memory
1012061 2024-07-01T15:18:20 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 1880 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;
	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]);
		}
	}

	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 FindSmart(vector<int> v) {
	FT f(*max_element(v.begin(), v.end()) + 1); 
	int mx = 0;
	for (int i = (int)v.size() - 1; i >= 0; i --) {
		mx = max(mx, f.query(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(FindBrute(A));
	}

	return res;
}

Compilation message

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 149 ms 348 KB Output is correct
2 Correct 539 ms 600 KB Output is correct
3 Correct 6889 ms 860 KB Output is correct
4 Correct 6978 ms 860 KB Output is correct
5 Correct 3115 ms 860 KB Output is correct
6 Correct 806 ms 1112 KB Output is correct
7 Correct 1631 ms 1104 KB Output is correct
8 Correct 2073 ms 912 KB Output is correct
9 Correct 3085 ms 856 KB Output is correct
10 Correct 7867 ms 832 KB Output is correct
11 Correct 8029 ms 840 KB Output is correct
12 Correct 8148 ms 856 KB Output is correct
13 Correct 8069 ms 832 KB Output is correct
14 Correct 8096 ms 808 KB Output is correct
15 Correct 8132 ms 600 KB Output is correct
16 Correct 8300 ms 600 KB Output is correct
17 Correct 8324 ms 856 KB Output is correct
18 Correct 8643 ms 604 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 348 KB Output is correct
2 Correct 539 ms 600 KB Output is correct
3 Correct 6889 ms 860 KB Output is correct
4 Correct 6978 ms 860 KB Output is correct
5 Correct 3115 ms 860 KB Output is correct
6 Correct 806 ms 1112 KB Output is correct
7 Correct 1631 ms 1104 KB Output is correct
8 Correct 2073 ms 912 KB Output is correct
9 Correct 3085 ms 856 KB Output is correct
10 Correct 7867 ms 832 KB Output is correct
11 Correct 8029 ms 840 KB Output is correct
12 Correct 8148 ms 856 KB Output is correct
13 Correct 8069 ms 832 KB Output is correct
14 Correct 8096 ms 808 KB Output is correct
15 Correct 8132 ms 600 KB Output is correct
16 Correct 8300 ms 600 KB Output is correct
17 Correct 8324 ms 856 KB Output is correct
18 Correct 8643 ms 604 KB Output is correct
19 Execution timed out 9026 ms 1880 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 348 KB Output is correct
2 Correct 539 ms 600 KB Output is correct
3 Correct 6889 ms 860 KB Output is correct
4 Correct 6978 ms 860 KB Output is correct
5 Correct 3115 ms 860 KB Output is correct
6 Correct 806 ms 1112 KB Output is correct
7 Correct 1631 ms 1104 KB Output is correct
8 Correct 2073 ms 912 KB Output is correct
9 Correct 3085 ms 856 KB Output is correct
10 Correct 7867 ms 832 KB Output is correct
11 Correct 8029 ms 840 KB Output is correct
12 Correct 8148 ms 856 KB Output is correct
13 Correct 8069 ms 832 KB Output is correct
14 Correct 8096 ms 808 KB Output is correct
15 Correct 8132 ms 600 KB Output is correct
16 Correct 8300 ms 600 KB Output is correct
17 Correct 8324 ms 856 KB Output is correct
18 Correct 8643 ms 604 KB Output is correct
19 Execution timed out 9026 ms 1880 KB Time limit exceeded
20 Halted 0 ms 0 KB -