oj.uz

Submission #198938

# Submission time Handle Problem Language Result Execution time Memory
198938 2020-01-28T08:36:31 Z kshitij_sodani Arranging Shoes (IOI19_shoes) C++17
10 / 100
 6 ms 1148 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef  long long  llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#include "shoes.h"
 
llo tree[100005];
long long n;
llo ss(llo i){
	llo tot=0;
	while(i<=2*n){
		tot+=tree[i];
		i+=(i&-i);
	}
	return tot;
}
void u(llo j){
	while(j>0){
		tree[j]+=1;
		j-=(j&-j);
	}
}
long long count_swaps(vector<int> s){
	n=s.size();
	n/=2;
    memset(tree,0,sizeof(tree));
	vector<llo> aa[n+1];
	vector<llo> bb[n+1];
	for(llo i=0;i<2*n;i++){
		if(s[i]<0){
			aa[-s[i]].pb(i);
		}
		else{
			bb[s[i]].pb(i);
		}
	}
	llo ind[n+1];
	llo ind2[n+1];
	long long tot=0;
	memset(ind,0,sizeof(ind));
	memset(ind2,0,sizeof(ind2));
	llo vis[2*n];
	memset(vis,0,sizeof(vis));
	for(llo i=0;i<2*n;i++){
		//cout<<i<<endl;
		if(vis[i]==1){
			continue;
		}
		else{
			if(s[i]<0){
				llo ind3=ind[abs(s[i])];
				llo j=aa[abs(s[i])][ind3];
				llo k=bb[abs(s[i])][ind3];
				llo co=ss(k+1)-ss(j+1);
				tot+=(k-j-1)-co;
				vis[j]=1;
				vis[k]=1;
				u(k+1);
				u(j+1);
 
			}
			else{
				llo ind3=ind2[abs(s[i])];
				llo j=aa[abs(s[i])][ind3];
				llo k=bb[abs(s[i])][ind3];
				llo co=ss(j+1)-ss(k+1);
			//	cout<<co<<endl;
				tot+=(j-k)-co;
				vis[j]=1;
				vis[k]=1;
				u(j+1);
				u(k+1);
			}
			ind[abs(s[i])]+=1;
			ind2[abs(s[i])]+=1;
	
		}
	}
	return tot;
 
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1144 KB Output is correct
2 Correct 6 ms 1144 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1144 KB Output is correct
2 Correct 6 ms 1144 KB Output is correct
3 Correct 5 ms 1148 KB Output is correct
4 Correct 6 ms 1144 KB Output is correct
5 Correct 6 ms 1144 KB Output is correct
6 Correct 5 ms 1144 KB Output is correct
7 Incorrect 6 ms 1140 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1144 KB Output is correct
2 Correct 6 ms 1144 KB Output is correct
3 Incorrect 6 ms 1144 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1144 KB Output is correct
2 Incorrect 6 ms 1016 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1144 KB Output is correct
2 Correct 6 ms 1144 KB Output is correct
3 Correct 5 ms 1148 KB Output is correct
4 Correct 6 ms 1144 KB Output is correct
5 Correct 6 ms 1144 KB Output is correct
6 Correct 5 ms 1144 KB Output is correct
7 Incorrect 6 ms 1140 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1144 KB Output is correct
2 Correct 6 ms 1144 KB Output is correct
3 Correct 5 ms 1148 KB Output is correct
4 Correct 6 ms 1144 KB Output is correct
5 Correct 6 ms 1144 KB Output is correct
6 Correct 5 ms 1144 KB Output is correct
7 Incorrect 6 ms 1140 KB Output isn't correct
8 Halted 0 ms 0 KB -