Submission #805600

#	Time	Username	Problem	Language	Result	Execution time	Memory
805600		Meloric	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	191 ms	27352 KiB

shoes

#include <bits/stdc++.h>
#define pb push_back
//#define int int64_t
#define pii pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(),(x).end()
#define lb lower_bound
#define ub upper_bound

using namespace std;

const int inf = 1e18;

void p(auto A){
	for(auto e : A)cout << e << ' ';
	cout << '\n';
}

int64_t count_swaps(vector<int> S){
	int n = S.size();
	vector<int>nxt(n, -1);
	map<int, vector<int>> mp;
	for(int i = 0; i< n; i++)mp[S[i]].pb(i);
	for(auto[k, v]:mp)if(k<0){
		vector<int>tmp = mp[-k];
		for(int i = 0; i< tmp.size(); i++){
			nxt[min(tmp[i], v[i])]=max(tmp[i], v[i]);
		}
	}
	vector<int>ft(n+5);
	auto upd = [&](int pos, int val){
		pos++;
		for(; pos <= n; pos+=pos&(-pos))ft[pos]+=val;
	};
	auto qer = [&](int pos){
		pos++;
		int ret = 0;
		for(;pos>0; pos-=pos&(-pos))ret+=ft[pos];
		return ret;
	};
	for(int i = 0; i< n; i++)upd(i, 1);
	vector<int> used(n);
	int64_t ans = 0;
	for(int i = 0; i< n; i++){
		if(used[i])continue;
		if(S[i]<0)upd(i, -1);
		ans+=qer(nxt[i]-1);
		if(S[i]>0)upd(i, -1);
		upd(nxt[i], -1);
		used[i]=1;
		used[nxt[i]]=1;
	}
	return ans;
}
/*
void solve(){
	int n; cin >> n;
	vector<int>A(2*n);
	for(int i = 0; i< 2*n; i++)cin >> A[i];
	cout << count_swaps(A);
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int t = 1;
	//cin >> t;
	while(t--)solve();
}
*/

Compilation message (stderr)

shoes.cpp:13:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   13 | const int inf = 1e18;
      |                 ^~~~
shoes.cpp:15:8: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   15 | void p(auto A){
      |        ^~~~
shoes.cpp: In function 'int64_t count_swaps(std::vector<int>)':
shoes.cpp:25:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |  for(auto[k, v]:mp)if(k<0){
      |          ^
shoes.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for(int i = 0; i< tmp.size(); i++){
      |                  ~^~~~~~~~~~~~

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