/**
 * Created with IntelliJ IDEA.
 * User: User
 * Date: 20.11.14
 * Time: 1:40
 * To change this template use File | Settings | File Templates.
 */
import java.io.*;
import java.util.*;

public class TestGen {
    final int MAX_N = 200000;
    final int MAX_M = 200000;
    final int MAX_VAL = 1000000000;
    int testCount;

    void print(int[] a, int[] l, int[] r) throws IOException {
        if (l.length != r.length || l.length == 0)
            throw new RuntimeException("Lengths don't equal or equal zero!");

        PrintWriter pw = new PrintWriter(String.format("../tests/%02d", ++testCount));
        System.out.println(testCount);
        pw.println(a.length + " " + l.length);
        for (int i = 0; i < a.length; i++) {
            pw.print(a[i]);
            if (i + 1 < a.length)
                pw.print(" ");
            else
                pw.println();
        }
        for (int i = 0; i < l.length; ++i)
            pw.println(l[i] + " " + r[i]);
        pw.close();
    }

    Random rnd = new Random(2539);

    void genSamples() throws IOException {
        int[] a = new int[] {3, 2, 1, 2, 3};
        int[] l = new int[] {1, 1, 3};
        int[] r = new int[] {5, 4, 5};
        print(a, l, r);

        int[] a1 = new int[] {6, 3, 6, 3, 2, 3};
        int[] l1 = new int[] {4, 2, 3, 1};
        int[] r1 = new int[] {4, 4, 6, 6};
        print(a1, l1, r1);
    }

    void genHandleTests() throws IOException {
        int[] a1 = new int[] {6, 6, 5, 2, 1, 2, 3, 10, 8, 8, 7, 10, 3, 9, 5, 4, 4, 5, 10, 11};
        int[] l1 = new int[] {4,  1,  1,  8,  8, 16};
        int[] r1 = new int[] {13, 2, 20, 11, 17, 17};
        print(a1, l1, r1);

        int[] a2 = new int[] {MAX_VAL, MAX_VAL, MAX_VAL - 1, MAX_VAL, MAX_VAL - 2, MAX_VAL - 3, MAX_VAL - 2, MAX_VAL - 30, MAX_VAL/3};
        int[] l2 = new int[] {1, 9, 2, 3, 3, 8};
        int[] r2 = new int[] {9, 9, 4, 6, 7, 8};
        print(a2, l2, r2);

        int[] a3 = new int[] {11, 4, 15, 9, 11, 2, 11, 13, 6, 12, 7, 13, 13, 11, 11};
        int[] l3 = new int[] {6,  1,  2, 7, 8, 9};
        int[] r3 = new int[] {8, 15, 14, 7, 8, 9};
        print(a3, l3, r3);
    }

    int[] genDiffNumsArray(int diffs, int maxval) {
        int[] a = new int[diffs];
        for (int i = 0; i < diffs; ++i)
            a[i] = rnd.nextInt(maxval) + 1;
        return a;
    }

    void genRandomQueries(int n, int m, int[] l, int[] r) {
        if (l.length != r.length || l.length != m)
            throw new RuntimeException("Lengths don't equal!");
        for (int i = 0; i < m; ++i) {
            int x = rnd.nextInt(n) + 1;
            int y = rnd.nextInt(n) + 1;
            if (x <= y) {
                l[i] = x;
                r[i] = y;
            }
            else {
                l[i] = y;
                r[i] = x;
            }
        }
    }

    void genTestsWithGroups(int n, int m, int diffs) throws IOException{
        int[] difNums = genDiffNumsArray(diffs, MAX_VAL);
        int[] a = new int[n];
        int[] l = new int[m];
        int[] r = new int[m];
        for (int i = 0; i < n; ++i) a[i] = MAX_VAL;
        int len = n / diffs;
        for (int i = 0; i < n; ++i)
            if (i / len < difNums.length)
                a[i] = difNums[i / len];
        genRandomQueries(n, m, l, r);
        print(a, l, r);
    }

    void genSawtoothTests(int n, int m, int diffs) throws IOException {
        int[] difNums = genDiffNumsArray(diffs, MAX_VAL);
        Arrays.sort(difNums);
        int[] a = new int[n];
        int[] l = new int[m];
        int[] r = new int[m];
        int sz = 0;
        int cur = rnd.nextInt(2);
        ArrayList <Integer> choose = new ArrayList<Integer>();
        while (sz < n) {
            choose.clear();
            int len = rnd.nextInt(Math.min(n - sz, diffs)) + 1;
            for (int i = 0; i < diffs && choose.size() < len; ++i)
                if (rnd.nextDouble() * diffs < len) choose.add(difNums[i]);
            for (int i = 0; i < choose.size(); ++i)
                if (cur == 0) a[i + sz] = choose.get(i);
                else a[i + sz] = choose.get(choose.size() - i - 1);
            sz += choose.size();
            cur = (cur + 1) % 2;
        }
        genRandomQueries(n, m, l, r);
        print(a, l, r);
    }

    void genCenterTest(int n, int m, int centers, boolean isLongCenter) throws IOException {
        Set <Integer> se = new HashSet<Integer>();
        int lenCenter = 3;
        if (isLongCenter)
            lenCenter = 10;

        int[] a = new int[n];
        int[] l = new int[m];
        int[] r = new int[m];
        int step = n / (centers + 1);
        for (int i = 0; i < centers; ++i) {
            int left = (i + 1) * step - lenCenter / 2;
            int right = (i + 1) * step + lenCenter / 2;
            int valCenter = rnd.nextInt(MAX_VAL) + 1;
            while (se.contains(valCenter))
                valCenter = rnd.nextInt(MAX_VAL) + 1;
            for (int j = left; j <= right; ++j)
                a[j] = valCenter;
            se.add(valCenter);
        }

        for (int i = 0; i < n;)
            if (a[i] == 0) {
                int len = rnd.nextInt(Math.min(n - i, lenCenter - 1)) + 1;
                int val = rnd.nextInt(MAX_VAL) + 1;
                while (se.contains(val))
                    val = rnd.nextInt(MAX_VAL) + 1;
                for (int j = 0; j < len && a[i + j] == 0; ++j)
                    a[i + j] = val;
                i += len;
                se.add(val);
            } else ++i;
        int queryStep = rnd.nextInt(Math.min(2 * (int)Math.sqrt(m), n / 2));
        for (int i = 0; i < m; ++i) {
            l[i] = rnd.nextInt(queryStep) + 1;
            r[i] = n - rnd.nextInt(queryStep);
        }
        print(a, l, r);
    }

    void genCyclicTest(int n, int m, int len) throws IOException {
        int[] nums = genDiffNumsArray(len, MAX_VAL);
        Arrays.sort(nums);
        int[] a = new int[n];
        int[] l = new int[m];
        int[] r = new int[m];
        genRandomQueries(n, m, l, r);

        if (rnd.nextInt() % 2 == 1)
            for (int i = 0; i < len / 2; ++i) {
                int tmp = nums[i];
                nums[i] = nums[len - i - 1];
                nums[len - i - 1] = tmp;
            }
        for (int i = 0; i < n; ++i) a[i] = nums[i % len];
        print(a, l, r);
    }

    void genConstTest(int n, int m, int val) throws IOException {
        int[] a = new int[n];
        int[] l = new int[m];
        int[] r = new int[m];
        for (int i = 0; i < n; ++i) a[i] = val;
        genRandomQueries(n, m, l, r);
        print(a, l, r);
    }

    void genRandomTest(int n, int m, int diffs) throws IOException {
        int[] difNums = genDiffNumsArray(diffs, MAX_VAL);
        int[] a = new int[n];
        int[] l = new int[m];
        int[] r = new int[m];
        for (int i = 0; i < n; ++i)
            a[i] = difNums[rnd.nextInt(diffs)];
        genRandomQueries(n, m, l, r);
        print(a, l, r);
    }

    void run() throws IOException {
        new File("../tests").mkdir();
        genSamples();
        genHandleTests();

        genTestsWithGroups(100, 100, 4);

        genSawtoothTests(100, 100, 3);
        genSawtoothTests(100, 100, 5);
        genSawtoothTests(300, 300, 20);

        genCenterTest(100, 100, 1, false);
        genCenterTest(100, 100, 2, false);
        genCenterTest(100, 100, 5, false);

        genCyclicTest(100, 100, 5);

        genTestsWithGroups(1000, 1000, 5);
        genTestsWithGroups(1000, 1000, 40);

        genCyclicTest(1000, 1000, 20);
        genCyclicTest(1000, 1000, 500);

        genCenterTest(1000, 1000, 1, false);
        genCenterTest(1000, 1000, 5, false);

        genSawtoothTests(3000, 3000, 10);
        genSawtoothTests(3000, 3000, 20);
        genSawtoothTests(3000, 3000, 50);


        genCenterTest(3000, 3000, 2, false);
        genCenterTest(3000, 3000, 10, false);

        genCyclicTest(3000, 3000, 100);

        genSawtoothTests(10000, 10000, 40);

        genTestsWithGroups(MAX_N / 2, MAX_M / 2, 200);
        genTestsWithGroups(MAX_N / 2, MAX_M / 2, 1000);

        genSawtoothTests(MAX_N / 2, MAX_M / 2, 170);
        genSawtoothTests(MAX_N / 2, MAX_M / 2, (int)Math.sqrt(MAX_N));
        genSawtoothTests(MAX_N / 2, MAX_M / 2, 1000);

        genCenterTest(MAX_N / 2, MAX_M / 2, 1, true);
        genCenterTest(MAX_N / 2, MAX_M / 2, 2, false);

        genCyclicTest(MAX_N / 2, MAX_M / 2, 100);
        genCyclicTest(MAX_N / 2, MAX_M / 2, (int)Math.sqrt(MAX_N));

        genConstTest(MAX_N / 2, MAX_M / 2, 1);
        genConstTest(MAX_N / 2, MAX_M / 2, MAX_VAL);

        int[] difs = new int[]{100, 300, 500, 1000, MAX_N / 2};
        for (int i = 0; i < 5; ++i)
            genRandomTest(MAX_N / 2, MAX_M / 2, difs[i]);
        genRandomTest(MAX_N, MAX_M, 100);
        genRandomTest(MAX_N, MAX_M, 300);
    }

    public static void main(String[] args) throws IOException {
        new TestGen().run();
    }
}

