Cod sursa(job #2208426)

Utilizator ZenusTudor Costin Razvan Zenus Data 29 mai 2018 18:49:43
Problema Radix Sort Scor 30
Compilator java Status done
Runda Arhiva educationala Marime 2.73 kb
import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }


    static int[] v = new int[10000000];
    static int[] count = new int[1<<16];
    static int[] tmp = new int[10000000];

    public static void main(String[] args) {

        try {

            InputStream targetStream = new FileInputStream(new File("radixsort.in"));
            InputReader input = new InputReader(targetStream);

            int N = input.nextInt(), A = input.nextInt(), B = input.nextInt(), C = input.nextInt();

            v[0] = B;
            for (int i = 1 ; i < N ; ++i){
                v[i] = (int)((1L * v[i-1] * A + B) % C);
                //System.out.println(v[i]);
            }

            for (int k = 0 ; k < 2 ; ++k){
                for (int i = 0 ; i < N ; ++i) {
                    int bucket = (v[i] >> (k << 4)) % (1 << 16);
                    //System.out.println(bucket);
                    count[bucket]++;
                }
                for (int i = (1 << 16) - 1 ; i > 0 ; --i){
                    count[i] = count[i-1];
                }
                count[0] = 0;
                for (int i = 2 ; i < (1 << 16) ; ++i){
                    count[i] += count[i-1];
                }

                for (int i = 0 ; i < N ; ++i){
                    int bucket = (v[i] >> (k << 4)) % (1 << 16);
                    tmp[count[bucket]] = v[i];
                    count[bucket]++;
                }

                for (int i = 0 ; i < (1 << 16) ; ++i){
                    count[i] = 0;
                }

                for (int i = 0 ; i < N ; ++i) {
                    v[i] = tmp[i];
                    //System.out.println(v[i]);
                }


            }

            PrintWriter fileOutput = new PrintWriter(new BufferedWriter(new FileWriter("radixsort.out")));
            for (int i = 0 ; i < N ; i += 10) {
                fileOutput.printf("%d " , v[i]);
            }
            fileOutput.printf("\n");
            fileOutput.close();
        }
        catch (IOException e) {}

    }
}