글 읽기 - 틀렸습니다..

znwlek 4년 전 0

안녕하세요~

다음과 같이 문제를 풀었는데...틀렸다고 나오는데 질문 게시판에 올라와있는 모든 case도 다 통과를 했거든요..

어디에서 틀렸는지 몰라서 글 올려봅니다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static Dwarf tree[];
	static int N, C;
	static ArrayList[] arr;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");

		N = Integer.parseInt(st.nextToken()); // 난쟁이 수
		C = Integer.parseInt(st.nextToken()); // 모자 수

		int h = 0;
		for (int i = 0; i < 10000000; i++) {
			if (Math.pow(i, 2) >= N) {
				h = (int) Math.pow(i, 2);
				break;
			}
		}

		arr = new ArrayList[C + 1];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = new ArrayList<Long>();
		}

		tree = new Dwarf[h * 4];
		for (int i = 0; i < h * 4; i++) {
			tree[i] = new Dwarf(0, 0);
		}

		st = new StringTokenizer(br.readLine().trim(), " ");
		for (int i = 1; i <= N; i++) {
			int val = Integer.parseInt(st.nextToken()); // 모자 색깔
			update(i, new Dwarf(val, 1), 1, 1, N);
			arr[val].add(i);
		}

		st = new StringTokenizer(br.readLine().trim(), " ");
		int size = Integer.parseInt(st.nextToken()); // 모자 색깔

		for (int i = 0; i < size; i++) {
			st = new StringTokenizer(br.readLine().trim(), " ");
			int a = Integer.parseInt(st.nextToken()); // 시작 난쟁이
			int b = Integer.parseInt(st.nextToken()); // 끝 난쟁이

			Dwarf temp = query(1, 1, N, a, b);
			if (temp.flag == 0) {
				System.out.println("no");
			} else {

//				int idx_l = search(arr[temp.color], a, 1);
//				int idx_r = search(arr[temp.color], b, 2);
				int idx_l = Collections.binarySearch(arr[temp.color], a);
				if(idx_l <0){
					idx_l = (idx_l * -1) -1;
				}
				int idx_r = Collections.binarySearch(arr[temp.color], b);
				if(idx_r <0){
					idx_r = (idx_r *-1) +1;
				}
				if (((b - a + 1) / 2) < (idx_r - idx_l + 1)) {
					System.out.println("yes " + temp.color);
				} else {
					System.out.println("no");
				}
			}

		}

	}

	public static int search(ArrayList arr2, int target, int flag) {
		int rtn = 0;
		int mid = 0;
		int left = 0;
		int right = arr2.size() - 1;
		
//		if(target < Integer.parseInt(arr2.get(left).toString())) {
//			return 0;
//		}
//		if(target > Integer.parseInt(arr2.get(right).toString())) {
//			return right;
//		}
		

		while (right >= left) {
			mid = (right + left) / 2;

			if (target == Integer.parseInt(arr2.get(mid).toString())) {
				return mid;
			}
			
			if (flag == 1) {
				if (target < Integer.parseInt(arr2.get(mid).toString())
						&& target > Integer.parseInt(arr2.get(mid - 1)
								.toString())) {
					return mid - 1;
				}
			} else {
				if (target > Integer.parseInt(arr2.get(mid).toString())
						&& target < Integer.parseInt(arr2.get(mid + 1)
								.toString())) {
					return mid + 1;
				}

			}
			// arr2.get(mid).toString()
			if (target < Integer.parseInt(arr2.get(mid).toString())) {
				right = mid - 1;
			} else {
				left = mid + 1;
			}
		}

		return left;
	}

	private static Dwarf query(int node, int start, int end, int left, int right) {
		// lers
		if (left > end || right < start)
			return new Dwarf(0, 0);

		// rels
		if (right >= end && left <= start)
			return tree[node];

		int mid = (start + end) / 2;

		return Compare(query(node * 2, start, mid, left, right),
				query(node * 2 + 1, mid + 1, end, left, right));
	}

	private static Dwarf update(int pos, Dwarf val, int node, int start, int end) {
		// peps
		if (pos > end || pos < start)
			return tree[node];

		if (start == end)
			return tree[node] = val;

		int mid = (start + end) / 2;

		return tree[node] = Compare(update(pos, val, node * 2, start, mid),
				update(pos, val, node * 2 + 1, mid + 1, end));
	}

	private static Dwarf Compare(Dwarf d1, Dwarf d2) {
		if (d1.color == d2.color) {
			return new Dwarf(d1.color, d1.flag + d2.flag);
		} else {
			if (Math.abs(d2.flag - d1.flag) == 0) {
				return new Dwarf(d2.color, 0);
			} else {
				if (d2.flag > d1.flag) {
					return d2;
				} else {
					return d1;
				}
			}
		}
	}

	static class Dwarf {
		public Dwarf(int color, int flag) {
			this.color = color;
			this.flag = flag;
		}

		int color;
		int flag;

		@Override
		public String toString() {
			return this.color + " / " + this.flag;
		}
	}
}

// 10 3
// 1 2 1 2 1 2 3 2 3 3
// 8
// 1 2
// 1 3
// 1 4
// 1 5
// 2 5
// 2 6
// 6 9
// 7 10

djm03178 4년 전 0

package는 지워야 하고, 클래스 이름은 Main이어야 합니다.

djm03178 4년 전 1

https://www.acmicpc.net/board/view/32737

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

틀렸습니다..

znwlek 4년 전 0

djm03178 4년 전 0

djm03178 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말