Submission #145770

#	Time	Username	Problem	Language	Result	Execution time	Memory
145770		AKaan37	Arranging Shoes (IOI19_shoes)	C++17	85 / 100	201 ms	31352 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"

using namespace std;

typedef long long lo;
typedef pair< lo,lo > PII;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(lo i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo MAX = -1000000000000000000;
const lo MIN = 1000000000000000000;
const lo inf = 1000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000007;

lo a[li],cev,hak[li],hak1[li],butun,butun1,farkli,farkli1,vis1[li],yer;
vector<int> vv;
map<lo ,lo > vis;
vector<PII> sag[li];
vector<PII> sol[li];

long long count_swaps(vector<int> v) {
	//~ cout<<"**\n";
	for(int i=0;i<(int)v.size();i++)vis1[abs(v[i])]++;
	//~ int cev=0;
	if(v.size()<=10005){
		for(lo i=0;i<(lo)v.size();i++){
			
			//~ cout<<butun<<endl;
			if(v[i]<0){
				if((lo)sag[-v[i]].size()-hak[-v[i]]>0){
					
					lo at=v[i];
					vis.clear();
					//~ cout<<sag[-v[i]][hak[-v[i]]-1].fi<<endl;
					vis.clear();
					for(lo j=i;j>0;j--){
						vis[v[j-1]]++;
						swap(v[j],v[j-1]);
						cev++;
						//~ cout<<vis[-at]<<" "<<i<<endl;
						if(vis[-at]==(lo)sag[-at].size()-hak[-at])break;
						//~ cout<<j<<" "<<j-1<<" "<<" "<<endl;
					}
					hak[-at]++;
					//~ cout<<"**\n";
				}
				else{sol[-v[i]].pb(mp(i,butun1));}
				
			}
			else{
				
				if((lo)sol[v[i]].size()-hak1[v[i]]>0){
					lo at=v[i];
					vis.clear();
					vis[v[i]]++;
					for(lo j=i;j>0;j--){
						
						if(vis[-at]==(lo)sol[at].size()-hak1[at])break;
						vis[v[j-1]]++;
						//~ cout<<(lo)sol[at].size()-hak1[at]<<" "<<vis[-at]<<" "<<i<<endl;
						if(vis[-at]==(lo)sol[at].size()-hak1[at])break;
						swap(v[j],v[j-1]);
						cev++;
					}
					hak1[at]++;
				}
				else{sag[v[i]].pb(mp(i,butun));}
			}
			
		}
	}
	
	
	else if(vis1[abs(v[0])]==(int)v.size()){
		for(lo i=0;i<(lo)v.size();i++){
			//~ cout<<"**\n";
			if(v[i]<0){
				//~ cout<<-v[i]<<endl;
				//~ cout<<sag[-v[i]][0].size<<" "<<sol[v[i]].size()<<endl;
				if((lo)sag[-v[i]].size()-hak[-v[i]]>0){cev+=i-sag[-v[i]][hak[-v[i]]].fi-sag[-v[i]][hak[-v[i]]].se;hak[-v[i]]++;}
				else sol[-v[i]].pb(mp(i,(lo)sol[-v[i]].size()-hak1[-v[i]]));
				
			}
			else{
				if((lo)sol[v[i]].size()-hak1[v[i]]>0){cev+=i-sol[v[i]][hak1[v[i]]].fi-1-sol[v[i]][hak1[v[i]]].se;hak1[v[i]]++;}
				else sag[v[i]].pb(mp(i,(lo)sag[v[i]].size()-hak[v[i]]));
			}
			
		}
	}
	else{
		for(lo i=0;i<(lo)v.size();i++){
			//~ cout<<"**\n";
			//~ cout<<butun<<endl;
			if(v[i]<0){
				//~ cout<<-v[i]<<endl;
				//~ cout<<sag[-v[i]][0].se<<" "<<sol[v[i]].size()<<endl;
				if((lo)sag[-v[i]].size()-hak[-v[i]]>0){butun--;cev+=i-sag[-v[i]][hak[-v[i]]].fi-sag[-v[i]][hak[-v[i]]].se+butun;hak[-v[i]]++;}
				else{sol[-v[i]].pb(mp(i,butun1));butun1++;}
				
			}
			else{
				if((lo)sol[v[i]].size()-hak1[v[i]]>0){butun1--;cev+=i-sol[v[i]][hak1[v[i]]].fi-1-sol[v[i]][hak1[v[i]]].se;hak1[v[i]]++;}
				else{sag[v[i]].pb(mp(i,butun));butun++;}
			}
		
		}
	}
	return cev;
}

//~ int main(){
	//~ lo n=0;
	//~ scanf("%lld",&n);
	//~ FOR{
		
		//~ scanf("%lld",&a[i]);
		//~ ////~ if(a[i]<0)
		//~ vv.pb(a[i]);
	//~ }
	//~ ////~ cout<<vv[0]<<endl;
	//~ lo at=count_swaps(vv);
	//~ printf("%lld\n",at);
//~ }

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