ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#199280 | #32. Sort | Dystractor | 0 | 3877ms | 43532kb | Java8 | 2.0kb | 2023-12-08 06:52:35 | 2023-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.