Submission #2247917


Source Code Expand

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskX solver = new TaskX();
		solver.solve(1, in, out);
		out.close();
	}

	static int count = 0;
	static class TaskX {
		public void solve(int testNumber, InputReader in, PrintWriter out) {

			int n = in.nextInt();
			int[] p = new int[n+1];
			for (int i = 0; i < n; i++) {
				p[i] = in.nextInt();
			}
			p[n] = -1;
			boolean[] isMatch = new boolean[n];
			for (int i = 0; i < n; i++) {
				if (p[i] == i+1) isMatch[i] = true;
			}

			for (int ban = 0; ban < n; ban++) {
				if (ban == 0) {
					if (isMatch[0]) {
						swap(p, 0, 1);
						ban++;
					}
				} else {
					if (isMatch[ban] && isMatch[ban+1]) {
						swap(p, ban, ban+1);
						ban++;
					} else if (isMatch[ban] && !isMatch[ban+1]) {
						swap(p, ban-1, ban);
					}
				}
			}
			out.println(count);

		}
	}
	static void swap(int[] p, int i, int j) {
		int tmp = p[i];
		p[i] = p[j];
		p[j] = tmp;
		count++;
	}

	static class ArrayUtils {
		public static Map<Integer, Integer> getCountMap(int[] array) {
			Map<Integer, Integer> map = new TreeMap<>();
			for (int x : array)
				map.merge(x, 1, Integer::sum);
			return map;
		}
	}

	static class InputReader {
		BufferedReader in;
		StringTokenizer tok;

		public String nextString() {
			while (!tok.hasMoreTokens()) {
				try {
					tok = new StringTokenizer(in.readLine(), " ");
				} catch (IOException e) {
					throw new InputMismatchException();
				}
			}
			return tok.nextToken();
		}

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

		public long nextLong() {
			return Long.parseLong(nextString());
		}

		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt();
			}
			return res;
		}

		public long[] nextLongArray(int n) {
			long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public InputReader(InputStream inputStream) {
			in = new BufferedReader(new InputStreamReader(inputStream));
			tok = new StringTokenizer("");
		}

	}

}

Submission Info

Submission Time
Task D - Derangement
User tutuz
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 2712 Byte
Status RE
Exec Time 171 ms
Memory 33768 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 4
AC × 11
RE × 4
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt
Case Name Status Exec Time Memory
0_000.txt AC 71 ms 21076 KB
0_001.txt AC 69 ms 19412 KB
0_002.txt AC 70 ms 17108 KB
0_003.txt AC 69 ms 17620 KB
1_004.txt RE 71 ms 19412 KB
1_005.txt AC 163 ms 32044 KB
1_006.txt AC 157 ms 32232 KB
1_007.txt AC 162 ms 30396 KB
1_008.txt RE 164 ms 33768 KB
1_009.txt RE 165 ms 32912 KB
1_010.txt AC 171 ms 33220 KB
1_011.txt RE 160 ms 33764 KB
1_012.txt AC 164 ms 30868 KB
1_013.txt AC 164 ms 31588 KB
1_014.txt AC 164 ms 32020 KB