Submission #1304991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304991		Johan	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	23 ms	9132 KiB

shoes

#include "shoes.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 5;
int len;
deque < int > b[350];
unordered_map < int , int > cnt[350];
void upd(int l, int r){
	int ll = l / len, rr = r / len;
	if(ll == rr){
		deque < int > d;
		for(int i = l % len; i <= r % len; i++)
			d.push_back(b[ll][i]);
		d.push_front(d.back());
		d.pop_back();
		int idx = 0;
		for(int i = l % len; i <= r % len; i++)
			b[ll][i] = d[idx++];
		return;
	}
	deque < int > x = {b[rr][r % len]};
	for(int i = l % len; i < len; i++){
		x.push_back(b[ll][i]);
	}
	int _idx = 0;
	for(int i = l % len; i < len; i++){
		b[ll][i] = x[_idx++];
	}
	int lst = x.back();
	cnt[ll][x.front()]++;
	cnt[ll][lst]--;
	for(int i = ll + 1; i <= rr - 1; i++){
		b[i].push_front(lst);
		cnt[i][lst]++;
		lst = b[i].back();
		b[i].pop_back();
		cnt[i][lst]--;
	}
	deque < int > y = {lst};
	for(int i = 0; i <= r % len; i++){
		y.push_back(b[rr][i]);
	}
	cnt[rr][lst]++;
	cnt[rr][y.back()]--;
	int idx_ = 0;
	for(int i = 0; i <= r % len; i++){
		b[rr][i] = y[idx_++];
	}
}
int ask(int l, int r, int x){
	int ll = l / len, rr = r / len;
//	cout << l << '-' << r << "<->" << ll << '-' << rr << endl;
	if(ll == rr){
		for(int i = l % len; i <= r % len; i++){
			if(b[ll][i] == x){
				return ll * len + i;
			}
		}
		return l;
	}
	for(int i = l % len; i < len; i++){
		if(b[ll][i] == x){
			return ll * len + i;
		}
	}
//	cout << "sonraki: ";
//	for(auto i : b[ll + 1])cout << i << '-';cout << endl;
//	cout << "dasssaqq: " << cnt[ll + 1][-9] << endl;
	int idx = -1;
	for(int i = ll + 1; i <= rr; i++){
		if(cnt[i][x] > 0){
			idx = i;
			break;
		}
	}
	if(idx != -1){
		for(int i = 0; i < len; i++){
			if(b[idx][i] == x){
				return idx * len + i;
			}
		}
	}
	for(int i = 0; i <= r % len; i++){
		if(b[rr][i] == x){
			return rr * len + i;
		}
	}
	return l;
}
long long count_swaps(vector < int > s){
	int n = s.size();
	len = sqrt(n + .0) + 1;
	for(int i = 0; i < n; i++){
		b[i / len].push_back(s[i]);
		cnt[i / len][s[i]]++;
	}
	long long ans = 0;
	for(int i = 0; i < n; i++){
		int si = b[i / len][i % len], si_ = si;
		if(i >= 1)
			si_ = b[(i - 1) / len][(i - 1) % len];
		if(si > 0 && i % 2 == 0){
			int j = ask(i, n - 1, -si);
			ans += (j - (i + 1) + 1);
//			cout << i << '-' << j << "--" << si << endl;
			upd(i, j);
		}
		else if(si < 0 && i % 2 == 1 || si > 0 && si != -si_){
			int j = ask(i, n - 1, -si_);
			ans += (j - (i + 1) + 1);
//			cout << i << '-' << j << endl;
			upd(i, j);
		}
//		for(int _ = 0; _ < len; _++){
//			for(auto __ : b[_])cout << __ << ' ';
//		}
//		cout << endl;
	}
	return ans;
}
/*
4
-6 9 -9 6 7 -6 6 -7
*/

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15