Pagini recente » Cod sursa (job #1743915) | Cod sursa (job #473495) | Cod sursa (job #2606591) | Cod sursa (job #2452178) | Cod sursa (job #2355609)
#include <iostream>
#include <fstream>
#include <stdint.h>
#include <string>
#include <algorithm>
#include <string.h>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
long long x[10000001];
long long dgs[256], idx[256];
long long x2[10000001];
int n, a, b, c;
uint8_t get_byte(int x, int b) {
return ((x >> (b * 8)) & 255);
}
void counting(long long a[],long long b[], int j) {
memset(dgs, 0, 256);
for (int i = 0; i < n; i++) {
dgs[get_byte(a[i], j)]++;
}
idx[0] = 0;
for (int i = 1; i < 256; i++)
idx[i] = idx[i - 1] + dgs[i - 1];
for (int i = 0; i < n; i++)
b[idx[get_byte(a[i],j)]++] = a[i];
}
void radix() {
for (uint8_t i = 0; i < 4; i++) {
if (i % 2 == 0) counting(x, x2, i);
else counting(x2, x, i);
}
}
void generate() {
x[0] = b % c;
for (int i = 1; i < n; i++)
x[i] = (a * x[i - 1] + b) % c;
}
void read() {
fin >> n >> a >> b >> c;
}
void write() {
for (int i = 0; i < n; i+=10) {
fout << x[i] << " ";
}
}
int main() {
read();
generate();
radix();
//sort(x, x + n);
write();
}
/*
::
/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