Pagini recente » Cod sursa (job #535872) | Cod sursa (job #723798) | Cod sursa (job #1574892) | Cod sursa (job #1350383) | Cod sursa (job #2355688)
#include <fstream>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
#define RADIX 0xFF
#define RADIX_SIZE 8
#define TOTAL_BYTES sizeof(numbers[0])
int n;
int numbers[10000001];
int get_byte(int d, int byte) {
return ((d >> (byte * 8))&RADIX);
}
void countsort(int A[], int B[], int byte) {
int counter[1 << RADIX_SIZE];
int index[1 << RADIX_SIZE];
memset(counter, 0, sizeof(counter));
for (int i = 0; i < n; i++)
++counter[get_byte(A[i],byte)];
index[0] = 0;
for (int i = 1; i < 1 << RADIX_SIZE; i++)
index[i] = index[i - 1] + counter[i - 1];
for (int i = 0; i < n; i++)
B[index[get_byte(A[i],byte)]++] = A[i];
}
void radixsort() {
int *temp = new int[n];
for (int i = 0; i < TOTAL_BYTES; i++) {
if (i % 2 == 0)
countsort(numbers, temp, i);
else
countsort(temp, numbers, i);
}
}
void read(){
int a, b, c;
fin >> n >> a >> b >> c;
numbers[0] = b % c;
for (int i = 1; i < n; i++)
numbers[i] = (1LL * a * numbers[i - 1] % c + b) % c;
}
void write(){
for (int i = 0; i < n; i += 10)
fout << numbers[i] << ' ';
}
int main(){
read();
radixsort();
write();
return 0;
}
/*
::
/dd/
odhhdo
`sdy..yds`
.yhhhhhhhhddhhhhddhhhhhhhhy.
.ydh/:+ddo::::::odd+:/hdy.
`sdy/dd+ +dd/yds`
oddd: :dddo
oddd: :dddo
`sdy/dd+ +dd/yds`
.ydh/:+ddo::::::odd+:/hdy.
.yhhhhhhhhddhhhhddhhhhhhhhy.
`sdy..yds`
odhhdo
/dd/
::
:+` `
````````.os-` .-------:----------...........-:+::...`..`````.-.....
.sooooo++sssso++++///////++++++sddysyyyyyyyyyyyyyyyyyysssssssssyyhhhhhhmmhssssyhssssss/`
`::::::::///++osss+++++oooossssyddmddmmmmmddddddddmNNmmmmmmmmmNNNNNNNNNNNmdddddmdddddmhy:
.// `.---:::/osyyysyhhhNNNNNNNMMMMMMMMMMMMMMMMMMMMNNdMMMMmhdd-
/ssssyddhhddyydddmNNmmmmmmmmmmmmmmmmmmmmmmmNNdddo
+yyyyy+///+mddmmmmNNNNmmmmmmmmNNNNNNNNNNNNNNMNmd/
`shhhhy:/:..``:ss/-:/os-``....-sh:-om/smNNmdmNh+-
.dddd/ `o .s .hNdddmM-
-dddd/ `-----::ymdddNm:
-dmmm/ +mmmmmNs`
:mmmm/ -hmddmNd.
:mmmm: `smmdmNN-
:mmmm: hNmdho`
/mmmm: `-.`
/mmmm-
+Nmmm-
+NNNm-
oNNNN.
oNNNN.
/ssss`
``
.yh.
:hh-
shh-
`hhd-
:dhd-
`shhd-
-hhhd-
/hhhh.
`shhhh.
.hhhhh.
/dhhhh`
shhhhh` `.
.hhhhhy` :s
:dhhhdy +o
+dhhhds `y/
`yhhhhds .h:
-hhhhhdo /d. `.
/dhhhhm+ sh. `:-`.......```
sdhhhdm/ `hy` `-:::/::::::::::-.`
`hhhhddm/ `..................````` :hs` .-:::///::::::::::/:-`
-dhhdddm: `...............................``` .-.````.``...```````````` `oh+ `.-::::::///:::::::::::/-`
/dhhdddm- `.............................---...`` .--.-:--.://:/::/+++//:::::-:-.......`` .sh/ .-:::/:::::/+/:::::::::::/:`
ohhhddmm. `........-.......................---...`` `````` .-```````/o/` :h-.-+//sossysosoo++//////::-.```````` -yd: `--:::::///::::++////::::/::/:`
`yhhhhdmy` `````````````````.........`````````````...............`........```````` ./:.`````.+/` -y.`.++ss+hddd:oyhhhy:----::sh-`..---.-+os+-``` .--:::::://::/:::+o////:::::::/:`
`yhhhddm: ```.----...........-.-----.---------..--.........-.............---------........-........../+////::::::::::::/+oo+/:-/+. -s.``//:osydhdooyhhhdy....-.oh/:--::://::-yhysoo++//:--..``` `--::::::///////::::oo://///:::::/-
sdhddm/ ``...------:------------------------------------------::::::-------------------------------------/yssssssssssssssssssyss+o: :h.`/::/+hNmhs/oysooyo``````sho++++oo++//shyyhhhhyyyyyyyyyyy/----..``` .--:::://///////////:+o:////::::::::`
+ddmm/ ``.----.......--------------------------------------------::::-::------------------------------------+hyyyyyyyyyyhyhhyyyhhyoy+.` :h./:-+yyysss++syyooo+-----:sh///++//::+hhhhhhhhhhhhhhhhhhhh+///////////:::-...``` `-://:--.`` `---:::://////////////:s//////:::::::/.
+mddd-.-...:+-....`````...---------------------------------------------------------------------------------------yhhhhhhhhhhhhhhyohhhh:./sy:` /h-/.:oso:--:+osyyoooo-:+oo/sh/::://++shhhhyyyyyyyyhhhhhhhhh////////////////s/:so++/:---..``` .://++++//:--..``` .--:::////////////////:/s//////::::::::-
`..:-:///:..../+```````..------------------------------------------------------------------------------------------shhhhhhhhhhhhhhhsyhhho:.++oso:` /y/-.//--:/ssosshhssoo/++++:yh/////+oyhhhhhhyyhyyyyyyyyyyhho////////////////sy`sNNmmmmd-+y////:::-..``` ``.-:/++o/:::--....```--:::://///////////////:oo:////::::::::::`
`-........`````.s.`````..------------------------------------------------------------------------::-----------------+hhhhhhhhhhhhhhhyhhhhyssoooo+oy+-` syo-:---:o+oyhosddhsooossss+yhoooooyhyoosssyyyyyyhhhhhhhhhy//////////////////d--NmmmmmNs`hs/////+/++/////::--..` ```..-::::---/s--/o/////////////////://:s//////::::::::::`
``...``````````````s:``...---------------------------------------------------------------------------------------------/ssssyyyhhhhhhhhhhhhhyyyssssso+oss/-sysso///ssosyhyymmdsooyyyyyoshososhhs:::::::::::::://+++os/:////////////////:d+`mmmmmmmd.+h///////++++++++++++++///:--.`` ``+s+oho-:o/-:////////////////oo/s/////:::::::::::`
`..`````````````......s/..-------------------------------------------------------------------------------------------------:::----::::::///+++oyyyyhhhyyyyyyyssyhhyhhhyyyyyyyyhhyyyyssyyyyyyosyhs/:::-...---:::::::-----::::::::::::::::::-ho hmmmmmdm:.d/////+/++///+++++++++++++++++++/+so/:-.` :dyys::/hooo++//////////++/+oooo////::::::::::::`
`/-````.............--.s+.--------------------------------------------------------------------------------------------------:/:::::::-:o+-:.-/+:-::::::///++oooo/++ooosssyyyyyyyhhhhhhhhhhhhyyhy+::::.`.`.``.:::::.`.`.....-::::::/o++///::-ss smmmmddm/`d/:///////////////++++++++/++++++/+yhhhhhyso+/:-.../shyh/:::+/+ssyysssoo++////////+ooooo++////:::::/.
-/-..------------------s+--------------------------------------------------------------------------------------------------:/://:::::::/.+o..-+:::::::::::::::::::::::::::::::::::://++++oossyo::::-`.`.````.:::-`````...````-::::://++ooossyo`ommmmmdmo`ho:/:::::::::::::::::://////////////yhhhhhhhhhhhhhhhhhdo:://///+osssyyyyyyyyyysso++++ooosssysssoo+/:.```
`.----------------------y/---------------------------------------------------------------------------------------------------////:::::::-`/soo.-:::::::::::::::::::::::::::::--:/++++/:--:::::::::::.`...````.:::.```.-:::-``.`-::::oo++//:::--.ommmmmdmo`/oooossssyo::::::::::::::::::::::::://++++ooossssyyyyyo////////++oosssssyyyyyyyyssoo++++++///++oosssoo++/::--.`` `
.-:::::::::::::::::::-:y::::::::::-----------------------------------------------------------------::::::::----------------:::::::::::/o-.:-+.+::::::::::::::::::::::::::::-/oysssshsoo/-::::::::::.``-.````.::-....-:::::-```.::::Nmmmmmmmmmdddmmmmmmmho+//:::-----::::::::::::::::::::::::::::::::::::::://////////+++++oooooooossso++/:/++ooossso++//::::::://+oooooooos+++/:-.``
`-::::::+:-.:/o+++/::-/y-::::::::::::-::-----------------------------------------------------------:/+++/:------:::::------:::::::::::/oo:oh//o:::::::::::::::::::::::::::.+soyyo+/dhssso--::::::::..-:-````.:::::::::::::-```.::::Nmmmmmmmmmmmmmmmmmmmmmmdmmddddddy:::::::::::::::::::::::::::::::::::::::/+oo++//++++++++++++oooooo+/:/ohsosssssoo+++//:::- ```...--:/-:://+++++/:`
`.::::++:ohhdms/dy/::so::::::::::::::::::--------------------------------------------------------::///+/:------:::::------::/:/:::::::+osydhs/::::::::::::::::::::::::::./ssso/oo:+hyssso.::::::::.:::-````.::::::::::::-.`.`.::::mmmmmmmmmmmmmmmmmmmmmmddmddddddmh:::::::::::::::::::::::::::::::::::::::///////////////++++oooo+/::/+ohyossssssoo+++///:/. `````````.
`//::++ddyhmd+ho:::y/:::::::::::::::::::::::::-::----------------------------------------------:::::::-------:::::------://////:::::///++//:::::::::::::::::::::::::::.osssssoymdssssss:-:::::::::::.````.:::::::::....```.:::::Nmmmmmmmmmmmmmmmmmmmmmmdmddddddmh-::::::::::::::::::::::::::::::::::::::////////////////+++o+/::/+oooodsooossssoo+++/////`
-mh:.--/oyydhhy:::+y:::::::::::::::::::::::::::::::::-::::::::---::------------------------::-:::://///::::::::::::::---//://////////////::::::::::::::::::::::::::::/.osssssshmmsyssss:-/::::::::::.````-:::::::::..`.`.`-:::::hhhhhddddddmmmmmmmddmmmddddddddmh:::::::::::::::::::::::::::::::::::::://:////////o////+++/:::/++++++shoooooooooo++++///-
.hh- `.--ohyhoo:::y+::::::::::::::::/:::::----:::::::-:-----:--::::::::::::::::::::::::---::-----::::::/://:::::::-----:/:/://///////////////:://://:::::::::::::///:/-/ssssssddmsyysso-::::::::::::.````-:::::::::::-..```-::::---------:::smdddddmhyyyhhhddddmh::::::::::::::::::::::::::::::::::::://:::::://:/+//++//::://///+/+/yy+oooooooooo+++++-
`yh. `.shh/-::s+::::::::::::::::///::::::::::::::-+sooo+++/////::::::-----------:::::::::::::::::::---::::::-::-----:://:://///////////////////////////////////////:-+ssydysssssyss:-/:::::::::::..`.`-:::::::::::::-```.:::/ssssssssss+`omdddddmo`---------:::::::::::::::::::::::::::::::::::::::+o:::::::::/+o+/::::///////////h++++oooooo++//:-.
`oh- -hyy--++::::::::::::::::://::::::::::::::::dNNNNNNNNNmmmmmddddhhhyyysssooo+++////:::::----:::::::::::::::::--:////////////////////////////////////////////////-/osssssssss+:://:::::::::::...`.:::-....-:::::-```.::::::::::::-ho ymdddddm+`hyssssssss+::::::::::::::::::::::::::::::::::::::::::::::::/+/:::::::::://////os////::--.```
.oh- /hh:`..-:::::::::::::::::::::::::::::::::/yyyhhdddmmdmmmmNNNmmNNNNNNNNNNNNmmmmmmmddddhhs/-::::::::::::::::::/+++++////////////////////////////////////////////:::++ooo+/::://////////::::...`.::::.```.::::-.```.::::::::::::-d/`mmmddddm:.d::::::::/:::::::::::::::::::::::::::::::::::::::::::::::::/::::::-..` `-:--...````
.oh- `sh+ `--::::::::::::::::::::::::::::::::::::::///////+++oooossyyhhhhdddddmmmmmmmmNNNo/:::::::::::::::::::++++++++++++++++++///////////////////////////////////:::::::////////////////-...../:::-`.``.....```.:::::::::::::/d.:Nmmdddmh`+y:::::::::::::::::::::::::::::::::::::::::::::::::::::::/:::---.``
.oy- -ds` `.--::::::::-------------:-:::--::::::-::::::::::::::::::::::::::://////++oso/::::::::::::::///+++o++++++++++++++++++++++oooo+++//////////////////////////////////////////////-...`-/::/:-.`.`...``.-::::::::::::::ss`smddmddN+.h+:::::::::::::::::::::::::::::::::::::::::::::::---.....+/.`
-ss` od- ``.--:::-------------------------------------::-:::::::::::::::::::---::::::::::::///++++++++++++++++/////////////////////++++ooo++++++////////////////////////////////////:::::/:///:/:-.....--:/::::::::::::::h-:ddddddmh.oy-::::::::::::::::::::::::::::::::::::----...``` `+/.````
-s+` -ho ``...-------------------------------------------------------:----:::::::://+++++////++++++++++++++++++/////::::::::::////////////++++o++++++//////////////////////////////////://:::/::::::::::::::::::::::so.yddddddd-/y::::::::::::::::::::::::::::---...``` .o/:ohdho-
.o- +h- ````...-------------------------------------------------------::-:/++++++++///////+//+///////////////////::::::::::::::::::///////////+++++oo+++++////////////////////////::::::::::::::::::::::::::::/:://////+/-+/:::::::::::::::---....```` .+////sshm/
`` .h+ ```````....----------------------------------------------/soooo+//:::::::::----::::::::::::::::::::::::::::::::::::::::::::////////////+++ooooo+++/////////////::::::::::::::::::::::::::::::::::::::::::::::----...````` .hdy+:::-dy`
/h. `-::----------------------------------------/+osso+:::::---------------::::::::::::::::::::::::::::::::::::::::::::::::::////////////++++ooooo++/////:::::::::::::::::::::::::::------....`````` `hmmd::::do
`y/ .-------------------------------------:////+oo+//:::-------------------:::::::::::::::::::::::::::::::::::::::::::::::::::://///////////::///s//::::::::::::::::::---...```` -yddhsyds`
/y `...-------------------------.``````.....---:/+//::::----------------------::::::::::::::::::::::::///+++++oo++++++/////:::::::::::://///::o/::::::::--..```` -/++:`
`y: `````````........``` `-/++++//::::::::--------------------------------:/+oossssssssssooooooooooooo++++//++/:::::::::/:---.``
:s` `/ooo++++//:::::::::------------------------:/ossssoooooooossossoosssoooooooooooooooooo+//::-`
`o. `.+yssossoo+//:::::::::::---------------:osssooooooooooooooooosssssssso+//:/ossooooo+ooo+//-``
` `.:+ydmNNMNhyhmmmmdhso/:---:::::-------.--/soooooooooooooooooooooooooo++/////-``.-:/+osso+//:/+++/:-.`
:oymNNNNNNNNNmys+hNNNNNNNNNmhhhhhddddhhhhyyyyyyyyhs+oooooooooooooooooooo++/+oyyyyyhhhhhyysssso++//+////:::-.``
-sdmmmmNNNNNNNNNNhyymNNNNNNNNNNmmmmdddhsyyyssosssyyhdosoossooooooooooooooooooooooooso/:------:::::-..-/+ooo+++//:--...`
.ymmmmmmmmmmmmmmmmmNNNmmmmmmmmmNNNNNNNNNNNmmdhyyso+/:::-/:::/++ooooooooooooooooooooooooooooooooooooooo++//-.--:/++//::-----..``
`odddddmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmddhyo+/::--:///++ooooooooooooooooooooooooooooooo+/:-------------:::-------...``
-ohhhhhhddddddddddddddddddddddddddddmdmmmmmmmmmmdddmdddmmmmmdhyo+/:--::://+oooooooooooooooooooooo/:----------------------:::::::-----..``
./oyyyhhhhhhhhhhhhhhhdddddddddddddddddddddddddhhddhhhddddddmmNNNmmhyo/-:::::////+ooooooooooso/---------------------------:::::::::::::----....```
`./+syyyyyhhhhhhhhhhhhhhhhhhhhhhhhhdddddddhhhddddddmmmNNNNNNNNNNNmmo` ```..---:::://++ooo+-------------------------------------::::::::::----------..```
``.:/+osssyyyyyyyyyyyyyyyyhhhhhhhhhhhhhhddmmmmNNNNNNNNNNNNNNNmmm+ ```..-::://:---------------------------------------------------------------..```
```.....---:::///++oooossssssyyyosmNNNNNNNNNNNmmmmmmmmmmmdh. ```.--::::::---------::/+++oooooooooo++++++++++///////::::::--------------..````
````````..```:ymmmmmmmmmNNNmmmmmmmNmdm/ ```.---::::-:+oooooosssssssooooooooooooooo++++++++++++++///::::-----------..```
`...---::///+++oossyyyyhy ``...-:/++oooooooooosssssssoooooooooooo++++++++++++++++++/////:::--------...``
```` ```.-::++oooooooooosssssssoooooooooooo++++++++///////++++//////::::-:---...```
```.-:/++oooo+oooossssssssoooooooooooooooooooooooooooo++++++++////:::::--..``
``..-://+++++++oooossssssssssyyyyyyyyssyyyyyyyyyyyyyyyyssssssooooo++++/:-..``
``..-:////////+ossyyyyyyyyyyyyyyyhyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyssoo/`
``..-::/+oosssssssyossyhssyssosssooooooooooooo+++++/////+/::::/-
`..-::////so/+soo////::::::::::----....`````
`
*/
Tempfli Levente2 leevii