oj.uz

Submission #647135

# Submission time Handle Problem Language Result Execution time Memory
647135 2022-10-01T16:35:02 Z Alma Ekoeko (COCI21_ekoeko) C++14
20 / 110
 1000 ms 2184 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
using ll = long long;
using ii = pair<int,int>;

const int INF = 1e9;
const ll LLINF = 1e18;
using vi = vector<int>;
using vvi = vector<vi>;

void setIO (string fileName) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    if (fileName != "std") {
        freopen((fileName + ".in").c_str(), "r", stdin);
        freopen((fileName + ".out").c_str(), "w", stdout);
    }
}

int n;
vi bit;

void update (int i, int val) {
	for (; i <= n; i += i&-i) {
		bit[i] += val;
	}
}

int query (int i) {
	int sum = 0;
	for (; i > 0; i -= i&-i) {
		sum += bit[i];
	}
	return sum;
}

int main() {
    setIO("std");

	cin >> n;
	n *= 2;
	string s;
	cin >> s;

	vi a(n), b, c;
	for (int i = 0; i < n; i++) {
		a[i] = s[i] - 'a';
	}
	c = a;
	sort(c.begin(), c.end());
	vi frec(26, 0);
	for (int i = 0; i < n; i += 2) {
		frec[c[i]]++;
	}
	for (int i = 0; i < n; i++) {
		if (frec[a[i]] > 0) {
			b.push_back(a[i]);
			frec[a[i]]--;
		}
	}
	vvi pos(26);
	for (int i = 0; i < n/2; i++) {
		b.push_back(b[i]);
		pos[b[i]].push_back(i);
	}
	for (int i = 0; i < n/2; i++) {
		b.push_back(b[i]);
		pos[b[i]].push_back(n/2 + i);
	}

	// turn a into b
	// obtain permutation -> count inversions

	vi perm(n);
	for (int i = 0; i < n; i++) {
		int idx = 0;
		for (int j = 0; j < (int)pos[a[i]].size(); j++) {
			if (pos[a[i]][j] == -1) continue;
			idx = pos[a[i]][j];
			break;
		}
		perm[i] = idx+1;
		for (int j = 0; j < (int)pos[a[i]].size(); j++) {
			if (pos[a[i]][j] == -1) continue;
			if (pos[a[i]][j] == idx) {
				pos[a[i]][j] = -1;
			}
		}
	}

	// for (int i = 0; i < n; i++) {
	// 	cout << a[i] << ' ';
	// } cout << '\n';

	// for (int i = 0; i < n; i++) {
	// 	cout << b[i] << ' ';
	// } cout << '\n';

	// for (int i = 0; i < n; i++) {
	// 	cout << perm[i] << ' ';
	// } cout << '\n';

	ll ans = 0;
	bit = vi(n+1, 0);
	for (int i = n-1; i >= 0; i--) {
		ans += query(perm[i]-1);
		update(perm[i], 1);
	}

	cout << ans << '\n';

    return 0;

	/*
	aaaabbbb
	aabb
	aaababbb
	aabbaabb
	*/
}

Compilation message

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen((fileName + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen((fileName + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1091 ms 2184 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1091 ms 2184 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1091 ms 2184 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1091 ms 2184 KB Time limit exceeded
3 Halted 0 ms 0 KB -