아이디어

• 각 질문에 대해, 중앙값을 기준으로 길이를 늘리다 비대칭이 되는 지점이 있으면 그 이후부터는 모두 비대칭이다.
• 모든 가능한 S, E 조합에 대해 위와 같은 논리를 적용해 답을 구한다.
  • 길이가 홀짝인 경우로 구분하는 것이 좋다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int N, A[], M, S, E;
	static boolean memo[][];
	
	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(rd.readLine());
		
		A = new int[N+1];
		tk = new StringTokenizer(rd.readLine());
		for (int i=1; i<=N; i++)
			A[i] = Integer.parseInt(tk.nextToken());
		
		memo = new boolean[N+1][N+1];
		for (int i=1; i<=N; i++) {
			int l, r;
			l = r = i;
			while (l >= 1 && r <= N && A[l] == A[r])
				memo[l--][r++] = true;
			l = i;
			r = i + 1;
			while (l >= 1 && r <= N && A[l] == A[r])
				memo[l--][r++] = true;
		}
		
		M = Integer.parseInt(rd.readLine());
		for (int i=0; i<M; i++) {
			tk = new StringTokenizer(rd.readLine());
			S = Integer.parseInt(tk.nextToken());
			E = Integer.parseInt(tk.nextToken());
			sb.append(memo[S][E] ? 1 : 0).append('\n');
		}
		
		System.out.println(sb);
	}
}

메모리 및 시간

• 메모리: 218628 KB
• 시간: 892 ms

리뷰

• 루프에 = 안 적어서 며칠동안 고민한거 실화??
• 그나저나 메모리는 그렇다 치고 시간도 엄청 빡빡하네... $O(N^2)$인데...
  * 메모리 진짜 아슬아슬하네