UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#199280#32. SortDystractor03877ms43532kbJava82.0kb2023-12-08 06:52:352023-12-08 06:52:37

answer

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int budget = 2 * (int) Math.pow(10, 7);
    static int totalCost = 0;
    static List<int[]> operations = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        quickSort(arr, 0, n - 1);
        operations.add(new int[]{-1, -1});
        for (int[] operation : operations) {
            bw.write(operation[0] + " " + operation[1] + "\n");
        }
        bw.write("\n");
        bw.flush();
    }

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j <= high - 1; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        int cost = high - (low - 1) + 1;
        if (totalCost + cost <= budget) {
            totalCost += cost;
            operations.add(new int[]{low + 1, high + 1});
        }
        return (i + 1);
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 0
Wrong Answer
time: 65ms
memory: 29996kb

input:

5
0 0 0 1 1

output:

1 5
1 3
2 3
-1 -1


result:

wrong answer Not sorted.

Test #2:

score: 0
Wrong Answer
time: 77ms
memory: 28212kb

input:

5
716816476 646500411 807499637 544792531 128057616

output:

1 5
2 5
2 3
-1 -1


result:

wrong answer Not sorted.

Test #3:

score: 0
Wrong Answer
time: 79ms
memory: 29656kb

input:

7
0 0 1 0 0 0 0

output:

1 7
2 7
3 7
4 7
4 6
5 6
-1 -1


result:

wrong answer Not sorted.

Test #4:

score: 0
Wrong Answer
time: 78ms
memory: 27740kb

input:

7
685386610 762888212 32009424 450956771 498508039 313999604 331164353

output:

1 7
1 2
4 7
4 5
-1 -1


result:

wrong answer Not sorted.

Test #5:

score: 0
Wrong Answer
time: 89ms
memory: 28724kb

input:

10
1 1 0 0 0 0 0 1 1 1

output:

1 10
1 5
2 5
3 5
4 5
7 10
8 10
9 10
-1 -1


result:

wrong answer Not sorted.

Test #6:

score: 0
Wrong Answer
time: 75ms
memory: 29600kb

input:

10
552474873 603523889 451688250 856980678 746716186 316583031 509750159 895158422 895128023 276991286

output:

1 10
2 10
2 4
2 3
6 10
8 10
9 10
-1 -1


result:

wrong answer Not sorted.

Test #7:

score: 0
Wrong Answer
time: 117ms
memory: 29320kb

input:

3000
774135042 955379290 425485912 951649655 435211761 517813461 22865164 126834432 859390051 751505...

output:

1 3000
1 2872
1 637
1 429
1 300
1 190
1 148
1 131
1 36
3 36
3 7
3 6
5 6
9 36
9 33
9 10
12 33
13 33
1...

result:

wrong answer Not sorted.

Test #8:

score: 0
Wrong Answer
time: 140ms
memory: 31456kb

input:

4000
0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 1 0 1 1 0 0 1 1...

output:

1 4000
2 4000
3 4000
3 2099
4 2099
5 2099
6 2099
7 2099
8 2099
9 2099
10 2099
11 2099
12 2099
13 209...

result:

wrong answer Not sorted.

Test #9:

score: 0
Wrong Answer
time: 130ms
memory: 35528kb

input:

4000
253876655 192406499 33773493 714588720 62247300 512617285 830025704 158991275 146203174 6211898...

output:

1 4000
1 12
1 4
1 2
6 12
6 8
7 8
10 12
14 4000
14 2447
14 266
14 161
14 49
14 38
14 36
14 17
16 17
1...

result:

wrong answer Not sorted.

Test #10:

score: 0
Wrong Answer
time: 133ms
memory: 31304kb

input:

5000
0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 1 1 0 0 1 0 0 0 1 1 0 1 1 1 1 0 1 1...

output:

1 5000
2 5000
3 5000
3 2522
4 2522
5 2522
6 2522
7 2522
8 2522
9 2522
10 2522
11 2522
12 2522
13 252...

result:

wrong answer Not sorted.

Test #11:

score: 0
Wrong Answer
time: 128ms
memory: 31264kb

input:

5000
576963277 817862335 430151834 505200145 307373684 896252967 779450344 424741325 188693368 71249...

output:

1 5000
1 4452
1 3536
1 2193
1 1373
1 172
1 86
1 39
1 38
1 12
1 8
1 3
1 2
5 8
7 8
10 12
14 38
14 17
1...

result:

wrong answer Not sorted.

Test #12:

score: 0
Wrong Answer
time: 176ms
memory: 32500kb

input:

5000
296887 701139 1259018 1624742 1747738 2354948 2616510 2777173 3193517 3454408 3801911 4078104 4...

output:

1 5000
2 5000
3 5000
5 5000
5 7
9 5000
9 15
9 13
9 11
17 5000
17 31
17 29
17 27
17 25
17 23
17 21
17...

result:

wrong answer Not sorted.

Test #13:

score: 0
Wrong Answer
time: 224ms
memory: 35616kb

input:

10000
1 1 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 0 0 0 1 0 1 1 ...

output:

1 10000
1 4960
2 4960
3 4960
4 4960
5 4960
6 4960
7 4960
8 4960
9 4960
10 4960
11 4960
12 4960
13 49...

result:

wrong answer Not sorted.

Test #14:

score: 0
Wrong Answer
time: 260ms
memory: 32372kb

input:

20000
0 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 0 0 ...

output:

1 20000
2 20000
3 20000
3 9977
4 9977
5 9977
6 9977
7 9977
8 9977
9 9977
10 9977
11 9977
12 9977
13 ...

result:

wrong answer Not sorted.

Test #15:

score: 0
Wrong Answer
time: 377ms
memory: 35244kb

input:

30000
1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 0 1 1 1 ...

output:

1 30000
2 30000
2 15017
3 15017
4 15017
5 15017
6 15017
7 15017
8 15017
9 15017
10 15017
11 15017
12...

result:

wrong answer Not sorted.

Test #16:

score: 0
Wrong Answer
time: 372ms
memory: 39372kb

input:

40000
0 1 0 0 0 1 0 1 1 1 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 ...

output:

1 40000
2 40000
3 40000
3 20063
4 20063
5 20063
6 20063
7 20063
8 20063
9 20063
10 20063
11 20063
12...

result:

wrong answer Not sorted.

Test #17:

score: 0
Wrong Answer
time: 517ms
memory: 38964kb

input:

50000
0 1 0 1 0 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0 1 0 0 1 1 0 1 1 0 0 1 1 0 1 0 0 1 0 ...

output:

1 50000
1 25253
2 25253
3 25253
4 25253
5 25253
6 25253
7 25253
8 25253
9 25253
10 25253
11 25253
12...

result:

wrong answer Not sorted.

Test #18:

score: 0
Wrong Answer
time: 280ms
memory: 35428kb

input:

30000
23333 23333 23333 23333 23333 23333 23333 23333 23333 23333 23333 23333 23333 23333 23333 2333...

output:

1 30000
1 22121
1 19529
1 19141
1 14567
1 12301
1 10499
1 10116
1 10080
1 10025
1 10022
1 10002
1 10...

result:

wrong answer Not sorted.

Test #19:

score: 0
Wrong Answer
time: 266ms
memory: 39752kb

input:

40000
45713484 162270600 502896796 450460958 129500884 513441781 557737624 340152311 679444775 35445...

output:

1 40000
1 7866
1 4951
1 1122
1 413
1 21
1 15
1 12
1 8
1 3
2 3
5 8
5 6
10 12
11 12
14 15
17 21
17 18
...

result:

wrong answer Not sorted.

Test #20:

score: 0
Wrong Answer
time: 294ms
memory: 43532kb

input:

50000
455891075 705915927 189674482 578895411 789714247 658466934 483470291 469989305 544838975 2828...

output:

1 50000
1 4306
1 2013
1 1830
1 1412
1 527
1 97
1 34
1 28
1 7
1 4
3 4
6 7
9 28
9 27
11 27
13 27
13 22...

result:

wrong answer Not sorted.