1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#include <iostream>
#include <vector>
#include <math.h>

//debug only
#include <fstream>
//#include <cstdlib>	//rand
//#include <time.h>       /* time */
//const char* trc= "<>";
//const char* trcLP= "LP";


enum mrowkaHeading {
	L_mrowka,
	P_mrowka,
};

struct mrowkaStruct{
	int odbic;
	 ///@see mrowkaHeading, 1=P>, 0=L<
	bool PL;
	mrowkaStruct(){};
	mrowkaStruct(const int odbic, const bool PL): odbic(odbic), PL(PL) {};
};

typedef std::vector<mrowkaStruct> mrowkiT;

 ///loads in input stream
void loadInput(std::istream& in, int& mrowki_count, mrowkiT& mrowki)
{
	in>> mrowki_count;
	mrowki.reserve(mrowki_count);

	char heading;
	for(int i=0; i!=mrowki_count; ++i){
		in>> heading;
//		mrowki.emplace_back(0, (heading=='P' || heading=='>') ? P_mrowka: L_mrowka);
		mrowki.emplace_back(0, (heading=='P' || heading=='>') );
	}
}


/* inline void swapPair(mrowkiT::iterator i1, mrowkiT::iterator i2)
{
	std::swap(i1->PL, i2->PL);	//swap to be <>, //we dont need this
	++i1->odbic;
	++i2->odbic;
}

 ///swaps PL heading of 2, and increases everything in between by 2
void swapAugmentSortMrowki(mrowkiT& mrowki)
{
	bool addL= true;
	mrowkiT::iterator lastL= mrowki.begin();
	for(mrowkiT::iterator iter=mrowki.begin(); iter!=mrowki.end(); ++iter){
		if(addL && !iter->PL){
			++lastL; //update lowest value
		}
		else {
			addL= false;
			if(!iter->PL){ // < is not on the lowest pos, so swap This<->lastL
				swapPair(iter, lastL);
				++lastL; //move to after newly inserted <
				for(auto iterPP=lastL; iterPP!=iter; ++iterPP){
					iterPP->odbic+= 2; //add 2 to everything in between
				}
			}
		}
	}
}*/

void swapAugmentBlockSortMrowki_addCount(mrowkiT::iterator& lastL, mrowkiT::iterator& modifyEnd, mrowkiT& mrowki, const int amountOfL)
{ // is the first > after a string of <<<
	if(modifyEnd== mrowki.end()) return; //not set
	 ///amount of P in between
	int diff= modifyEnd- lastL;
	const int halfedDiff= (diff/2)+ 1;
	int incrementBy= 1;
	int amountOfLToMove= amountOfL;
	const int amountOfP=	(modifyEnd-amountOfL) - lastL +1;
//	const int amountOfLOnBegin= (modifyEnd-amountOfL) - mrowki.begin();	//mod begin - start = amount of items before that we can swap with
	amountOfLToMove= std::min(amountOfLToMove, amountOfP);

	mrowkiT::iterator frontIter= lastL;
	mrowkiT::iterator backIter= modifyEnd;
	for(int i=0; i!=halfedDiff; ++i){	//each iteration swaps 1 pair
		frontIter->odbic+= incrementBy;
		if(frontIter == backIter) //only 1 element left to change
			break;

		backIter->odbic+= incrementBy;
		++frontIter;
		--backIter;
		if(amountOfLToMove>1){
			incrementBy+= 2 -(frontIter == backIter);
		}
		else if(amountOfLToMove==1){
			incrementBy+= 1;
		}
		else { //nothing
			continue;
		}
		--amountOfLToMove;
	}
	// update lowest bound
	 //add amount of L swapped
	lastL+= amountOfL;
	modifyEnd= mrowki.end();
}
 ///swaps PL heading of 2, and increases everything in between by 2
void swapAugmentBlockSortMrowki(mrowkiT& mrowki)
{
	bool addL= true;
	mrowkiT::iterator lastL= mrowki.begin();
	mrowkiT::iterator modifyEnd= mrowki.end();
	int amountOfL= 0;
	for(mrowkiT::iterator iter=mrowki.begin(); iter!=mrowki.end(); ++iter){
		if(addL && !iter->PL){
			++lastL; //update lowest value
		}
		else {
			addL= false;
			if(!iter->PL){ // < is not on the lowest pos, so swap This<->lastL
				modifyEnd= iter;
				++amountOfL;
			}
			else { // is the first > after a string of <<<
				swapAugmentBlockSortMrowki_addCount(lastL, modifyEnd, mrowki, amountOfL);
				amountOfL= 0;
			}
		}
	}
	//make sure to finish and call this again
	swapAugmentBlockSortMrowki_addCount(lastL, modifyEnd, mrowki, amountOfL);
}


void singleTest(std::istream& inputStr, std::ostream& outStr)
{
	int mrowki_count;
	mrowkiT mrowki;

	loadInput(inputStr, mrowki_count, mrowki);

 //single iter, with (L to i)<n updater,	so about n*(amount L not in right place *n), best n+1, worst n*n
//	swapAugmentSortMrowki(mrowki);		//29.382 s
	swapAugmentBlockSortMrowki(mrowki);	//18.915 s	//17.19 s (no print)

 //print out results, time effect is negligible (but using std::endl slows it down by ~15% but that will heavily depend on the disk used)
	for(int i=0; i!=mrowki_count; ++i){
		outStr<< mrowki.at(i).odbic;
		if(i+1 != mrowki_count)
			outStr<< " ";
	}
	outStr<< "\n";
}
/*void multipleTests()
{
	std::ifstream inFile;
	std::ofstream outFile;
	std::string pathIn= "V:\\tests\\in\\";
	std::string pathOut= "V:\\tests\\results\\";
	for(int i=0; i<= 649; ++i){
		inFile.open(pathIn+ std::__cxx11::to_string(i) +".in");
		outFile.open(pathOut+ std::__cxx11::to_string(i) +".out");
		singleTest(inFile, outFile);
		inFile.close();
		outFile.close();
	}
}*/

int main()
{
//	multipleTests();
//	return -1;
	//6 LPPLPL		0 1 3 3 2 1
	//8 LPPLLPLL	0 1 3 4 4 4 3 1
	//9 LPPPPPLLP	0 1 3 4 4 4 3 1 0

//	std::ifstream in("test400.txt");	//400k swapAugmentBlockSortMrowki takes 0.101 sec
//	std::ofstream resOut("results.txt");
//	singleTest(in, resOut);

	singleTest(std::cin, std::cout);

	return 0;
}