Submission #3217685
Source Code Expand
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.*; class Main{ static void solve(){ int n = ni(); Deque<Integer> que = new ArrayDeque<>(); for(int i=0;i<n;++i)que.addLast(ni()); List<Integer> ans = new ArrayList<>(); int cnt=0; while(true){ if(que.peekFirst()==0){ Integer[] array = que.toArray(new Integer[n]); for(int i=0;i<n;++i){ if(array[i]!=i)break; if(i==n-1){ out.println(ans.size()); for(int a: ans)out.println(a); return; } } } if(que.peekFirst()<que.peekLast() && que.peekFirst()>0){ ans.add(n-1); int f = que.pollFirst(), l=que.pollLast(); que.addFirst(l);que.addLast(f); cnt=0; } ans.add(1); que.addLast(que.pollFirst()); } } public static void main(String[] args){ solve(); out.flush(); } private static InputStream in = System.in; private static PrintWriter out = new PrintWriter(System.out); static boolean inrange(int y, int x, int h, int w){ return y>=0 && y<h && x>=0 && x<w; } @SuppressWarnings("unchecked") static<T extends Comparable> int lower_bound(List<T> list, T key){ int lower=-1;int upper=list.size(); while(upper - lower>1){ int center =(upper+lower)/2; if(list.get(center).compareTo(key)>=0)upper=center; else lower=center; } return upper; } @SuppressWarnings("unchecked") static <T extends Comparable> int upper_bound(List<T> list, T key){ int lower=-1;int upper=list.size(); while(upper-lower >1){ int center=(upper+lower)/2; if(list.get(center).compareTo(key)>0)upper=center; else lower=center; } return upper; } @SuppressWarnings("unchecked") static <T extends Comparable> boolean next_permutation(List<T> list){ int lastIndex = list.size()-2; while(lastIndex>=0 && list.get(lastIndex).compareTo(list.get(lastIndex+1))>=0)--lastIndex; if(lastIndex<0)return false; int swapIndex = list.size()-1; while(list.get(lastIndex).compareTo(list.get(swapIndex))>=0)swapIndex--; T tmp = list.get(lastIndex); list.set(lastIndex++, list.get(swapIndex)); list.set(swapIndex, tmp); swapIndex = list.size()-1; while(lastIndex<swapIndex){ tmp = list.get(lastIndex); list.set(lastIndex, list.get(swapIndex)); list.set(swapIndex, tmp); ++lastIndex;--swapIndex; } return true; } private static final byte[] buffer = new byte[1<<15]; private static int ptr = 0; private static int buflen = 0; private static boolean hasNextByte(){ if(ptr<buflen)return true; ptr = 0; try{ buflen = in.read(buffer); } catch (IOException e){ e.printStackTrace(); } return buflen>0; } private static int readByte(){ if(hasNextByte()) return buffer[ptr++]; else return -1;} private static boolean isSpaceChar(int c){ return !(33<=c && c<=126);} private static int skip(){int res; while((res=readByte())!=-1 && isSpaceChar(res)); return res;} private static double nd(){ return Double.parseDouble(ns()); } private static char nc(){ return (char)skip(); } private static String ns(){ StringBuilder sb = new StringBuilder(); for(int b=skip();!isSpaceChar(b);b=readByte())sb.append((char)b); return sb.toString(); } private static int[] nia(int n){ int[] res = new int[n]; for(int i=0;i<n;++i)res[i]=ni(); return res; } private static long[] nla(int n){ long[] res = new long[n]; for(int i=0;i<n;++i)res[i]=nl(); return res; } private static int ni(){ int res=0,b; boolean minus=false; while((b=readByte())!=-1 && !((b>='0'&&b<='9') || b=='-')); if(b=='-'){ minus=true; b=readByte(); } for(;'0'<=b&&b<='9';b=readByte())res=res*10+(b-'0'); return minus ? -res:res; } private static long nl(){ long res=0,b; boolean minus=false; while((b=readByte())!=-1 && !((b>='0'&&b<='9') || b=='-')); if(b=='-'){ minus=true; b=readByte(); } for(;'0'<=b&&b<='9';b=readByte())res=res*10+(b-'0'); return minus ? -res:res; } }
Submission Info
Submission Time | |
---|---|
Task | B - Many Swaps Sorting |
User | inmir |
Language | Java8 (OpenJDK 1.8.0) |
Score | 900 |
Code Size | 4299 Byte |
Status | AC |
Exec Time | 155 ms |
Memory | 26580 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 300 / 300 | 400 / 400 | 200 / 200 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt |
Subtask1 | 00_example_01.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt |
Subtask2 | 00_example_01.txt, 00_example_02.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s2_07.txt, s2_08.txt, s2_09.txt, s2_10.txt, s2_11.txt |
All | 00_example_01.txt, 00_example_02.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s2_07.txt, s2_08.txt, s2_09.txt, s2_10.txt, s2_11.txt, s3_12.txt, s3_13.txt, s3_14.txt, s3_15.txt, s3_16.txt, s3_17.txt, s3_18.txt, s3_19.txt, s3_20.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_example_01.txt | AC | 69 ms | 19156 KB |
00_example_02.txt | AC | 69 ms | 19412 KB |
s1_01.txt | AC | 69 ms | 18260 KB |
s1_02.txt | AC | 70 ms | 20308 KB |
s1_03.txt | AC | 70 ms | 19796 KB |
s1_04.txt | AC | 69 ms | 19412 KB |
s1_05.txt | AC | 71 ms | 19540 KB |
s1_06.txt | AC | 68 ms | 21204 KB |
s2_07.txt | AC | 70 ms | 21332 KB |
s2_08.txt | AC | 73 ms | 18004 KB |
s2_09.txt | AC | 85 ms | 18644 KB |
s2_10.txt | AC | 75 ms | 21460 KB |
s2_11.txt | AC | 87 ms | 19156 KB |
s3_12.txt | AC | 102 ms | 20820 KB |
s3_13.txt | AC | 115 ms | 21204 KB |
s3_14.txt | AC | 96 ms | 17492 KB |
s3_15.txt | AC | 94 ms | 19028 KB |
s3_16.txt | AC | 155 ms | 24364 KB |
s3_17.txt | AC | 148 ms | 21460 KB |
s3_18.txt | AC | 140 ms | 25172 KB |
s3_19.txt | AC | 144 ms | 26580 KB |
s3_20.txt | AC | 70 ms | 18004 KB |