oj.uz

Submission #815694

# Submission time Handle Problem Language Result Execution time Memory
815694 2023-08-08T18:54:18 Z Edu175 Arranging Shoes (IOI19_shoes) C++17
10 / 100
 1 ms 300 KB 
#include "shoes.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) for(auto sdg:v)cout<<sdg<<" ";cout<<"\n"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;

vector<ll>a,p,pos; // permutation, position of idx
void move(ll i, ll j){ //move i to pos j by swapping j<i
	//cout<<"move "<<i<<" "<<j<<"\n";
	while(j<pos[i]){
		ll &ant=p[pos[i]-1];
		swap(pos[ant],pos[i]);
		swap(ant,p[i]);
	}
}
long long count_swaps(vector<int> S){
	for(auto i:S)a.pb(i);
	ll n=SZ(a)/2;
	fore(i,0,2*n)p.pb(i),pos.pb(i);
	vector<ll> l[n+1],r[n+1];
	ll res=0;
	fore(i,0,2*n){
		ll s=abs(a[i]);
		//cout<<i<<" "<<a[i]<<": "<<s<<"\n";
		//imp(p); imp(pos);
		if(a[i]<0){
			//cout<<"l\n";
			//imp(r[s]);
			if(!SZ(r[s]))l[s].pb(i);
			else {
				ll j=r[s].back(); r[s].pop_back();
				res+=i-pos[j];
				move(i,pos[j]);
			}
		}
		else {
			//cout<<"r\n";
			//imp(l[s]);
			if(!SZ(l[s]))r[s].pb(i);
			else {
				ll j=l[s].back(); l[s].pop_back();
				res+=i-(pos[j]+1);
				move(i,pos[j]+1);
			}
		}
		/*fore(i,0,n+1){
			cout<<"l["<<i<<"]: "; imp(l[i]);
			cout<<"r["<<i<<"]: "; imp(r[i]);
		}*/
	}
	return res;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 296 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 0 ms 300 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Incorrect 0 ms 212 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 296 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 0 ms 300 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Incorrect 0 ms 212 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 296 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 0 ms 300 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Incorrect 0 ms 212 KB Output isn't correct
15 Halted 0 ms 0 KB -