제출 #1097997

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1097997		Noname_1900	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	109 ms	79520 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
const int NMAX = 100000;
queue<int> posDroites[NMAX+1];
int posGauche[NMAX];
int arbre[NMAX*3*2];
int push[NMAX*3*2];
pair<int, int> debFin[NMAX*3*2];
void init(int noeud, int deb, int fin)
{
	debFin[noeud] = {deb, fin};
	if(deb == fin-1)	return;
	int mil = (deb+fin)/2;
	init(noeud*2, deb, mil);
	init(noeud*2+1, mil, fin);
}
int trouver(int noeud, int deb, int fin)
{
	arbre[noeud] += push[noeud];
	if(debFin[noeud].first != debFin[noeud].second-1)
	{
		push[noeud*2] += push[noeud];
		push[noeud*2+1] += push[noeud];
	}
	push[noeud] = 0;
	if((debFin[noeud].first >= fin) || (debFin[noeud].second <= deb))	return 0;
	if((debFin[noeud].first >= deb) && (debFin[noeud].second <= fin))	return arbre[noeud];
	return trouver(noeud*2,deb, fin)+trouver(noeud*2+1, deb, fin);
}
int chang(int noeud, int deb, int fin)
{
	arbre[noeud] += push[noeud];
	if(debFin[noeud].first != debFin[noeud].second-1)
	{
		push[noeud*2] += push[noeud];
		push[noeud*2+1] += push[noeud];
	}
	push[noeud] = 0;
	if((debFin[noeud].first >= fin) || (debFin[noeud].second <= deb))	return arbre[noeud];
	if((debFin[noeud].first >= deb) && (debFin[noeud].second <= fin))	
	{
		push[noeud]++;
		return arbre[noeud]+1;
	}
	return arbre[noeud] = chang(noeud*2,deb, fin)+chang(noeud*2+1, deb, fin);
}
long long count_swaps(std::vector<int> s) {
	int nbVal = s.size()/2;
	int nbG = 0;
	for(int a = 0; a < s.size(); a++)
	{
		int i = s[a];
		if(i > 0)
		{
			posDroites[i].push(a);
		}
		else
		{
			posGauche[nbG] = a;	
			nbG++;
		}
	}
	//cout << "okmj" << endl;
	long long somme = 0;
	//int decalage = 0;
	init(1, 0, s.size());
	for(int iPair = 0; iPair < nbVal; iPair++)
	{
		int pos1 = posGauche[iPair]+trouver(1, posGauche[iPair], posGauche[iPair]+1);
		//cout << pos1 << " ";
		somme += (pos1-iPair*2);
		int type = abs(s[posGauche[iPair]]);
		//cout << posDroites[type].front()+trouver(1, posDroites[type].front(), posDroites[type].front()+1) << endl;
		
		
		chang(1, 0, pos1);
		
		int pos2 = posDroites[type].front()+trouver(1, posDroites[type].front(), posDroites[type].front()+1);
		somme += (pos2-(iPair*2+1));
		//cout << pos2 << endl;
		chang(1, 0, pos2);
		posDroites[type].pop();
		//somme += (pos2-pos1)-1;
		//cout << "res : " << ((pos1-iPair*2)) << " " << (pos2-(iPair*2+1)) << " " << somme << endl;
	}
	return somme;
}

컴파일 시 표준 에러 (stderr) 메시지

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int a = 0; a < s.size(); a++)
      |                 ~~^~~~~~~~~~

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