글 읽기 - 채점 컴퓨터가 리눅스가 아닌가요?

shjgkwo 9년 전 0

제가 가진 데이터는 전부 답이 나왔는데

여기선 자꾸 틀렸다고 하네요 ㅠㅠ

혹시 채점 컴퓨터가 리눅스가 아닌가요?

#include <stdio.h>
#include <algorithm>
using namespace std;
struct bung {
    int x;
    int y;
    int num;
};
bool fsort(bung a, bung b) {
    if (a.x < b.x) return true;
    if (a.x <= b.x && a.y > b.y) return true;
    return false;
}
bung max1, tree[6200000], o[1120000];
int n, m;
int moth[1120000];
int son[1120000];
int chk[1120000];
int min1 = 0x7fffffff;
void _find(int x) {
    int d = x, e = 0, tmp;
    int st, ed, mid;
    while (d) {
        chk[e++] = o[d].x;
        if (o[d].y > m) {
            tmp = o[d].y - m;
            st = 1;
            ed = e;
            while (st < ed) {
                mid = (st + ed) / 2;
                if (tmp == chk[mid - 1]) break;
                if (tmp < chk[mid - 1]) ed = mid;
                if (tmp > chk[mid - 1]) {
                    if (st == mid) break;
                    st = mid;
                }
            }
            if (st == ed) mid = st;
            if (tmp >= chk[mid - 1] && min1 > e - mid + 1) min1 = e - mid + 1;
        }
        d = moth[d];
    }
}
int main() {
    int i;
    int maxy;
    int d;
    int k;
    int nx, ny, nnum;
    int st, ed;
    freopen("input.txt","rt",stdin);
    scanf("%d %d", &m, &n);
    for (k = 1; k < m * 2; k <<= 1);
    for (i = 1; i <= n; i++) {
        moth[i] = -1;
        scanf("%d %d", &o[i].x, &o[i].y);
        if (o[i].x > o[i].y) o[i].y += m;
        else {
            o[i].x += m;
            o[i].y += m;
        }
        o[i].y++;
    }
    std::sort(o + 1, o + n + 1, fsort);
    maxy = o[1].y;
    if (o[1].x > m && o[1].y > m) {
        o[1].x -= m;
        o[1].y -= m;
    }
    for (i = 2; i <= n; i++) {
        if (o[i].y <= maxy) o[i].x = 0x7fffffff;
        else maxy = o[i].y;

        if (o[i].x != 0x7fffffff && o[i].x > m && o[i].y > m) {
            o[i].x -= m;
            o[i].y -= m;
        }
    }
    std::sort(o + 1, o + n + 1, fsort);
    for (i = 1; i <= n; i++) {
        if(o[i].x == 0x7fffffff) break;
        o[i].num = i;

        d = k + o[i].x - 1;
        tree[d].x = o[i].x;
        tree[d].y = o[i].y;
        tree[d].num = o[i].num;
        while (d > 1) {
            if (tree[d / 2].y < tree[d].y) tree[d / 2] = tree[d];
            d /= 2;
        }
    }
    for (i = 1; i <= n; i++) {
        if (o[i].x == 0x7fffffff) break;
        if (moth[i] != -1) continue;
        nx = o[i].x;
        ny = o[i].y;
        nnum = o[i].num;
        while (1) {
            max1.num = 0;
            max1.x = 0;
            max1.y = 0;

            st = k + nx;
            ed = k + ny - 1;
            while (1) {
                if (max1.y < tree[st].y) max1 = tree[st];
                if (max1.y < tree[ed].y) max1 = tree[ed];
                if (st == ed) break;
                if (st & 1) st++;
                if (!(ed & 1)) ed--;
                if (st > ed) break;
                st /= 2;
                ed /= 2;
            }

            if (max1.num == 0) {
                moth[nnum] = 0;
                break;
            }
            son[max1.num]++;
            moth[nnum] = max1.num;
            if (moth[max1.num] != -1) break;
            nx = max1.x;
            ny = max1.y;
            nnum = max1.num;
        }
    }
    for (i = 1; i <= n; i++) {
        if (o[i].x == 0x7fffffff) break;
        if (son[i]) continue;
        _find(i);
    }
    if(min1 != 0x7fffffff) printf("%d", min1);
    else printf("impossible");
    return 0;
}

pichulia 9년 전 1

https://icpcarchive.ecs.baylor.edu/index.php?optio...

여기서 채점하니까 틀렸다고 나오네요...

무슨 뜻이냐면..

알고리즘이 틀렸다는 얘기지요....

제가 저 문제 풀이를 모르기 때문에 어디가 틀렸다! 하고 알려줄 순 없을거같네요..ㅠㅠ

참고로 채점서버는 리눅스가 맞습니다.

shjgkwo 9년 전 0

감사합니다 ㅠㅠ

덕분에 풀었어요!!!

그 이분탐색으로 찾지 않고 인덱스 트리로 찾으니 됐네요!

알고리즘이 잘못됐네요 ㅠㅠ

지금 생각해보니 중복처리를 안해서.. ㅠㅠ

shjgkwo 9년 전 0

그런데 알려주신 사이트에서 채점하니 그쪽은 여전히 WA 나오네요 ㅠㅠ

제 소스 전체적인 부분이 틀린걸로 보아

이쪽 서버 데이터가 부족한가 보네요...

#include <stdio.h>
#include <algorithm>
using namespace std;
struct bung {
    int x;
    int y;
    int num;
};
bool fsort(bung a, bung b) {
    if (a.x < b.x) return true;
    if (a.x <= b.x && a.y > b.y) return true;
    return false;
}
bung max1, tree[4300000], o[1120000];
int n, m;
int k;
int moth[1120000];
int son[1120000];
int chk[4120000];
int min1 = 0x7fffffff;
void _find(int x) {
    int d = x, tmp, e = 0;
    int w;
    int st, ed;
    int max2;
    while (d) {
    	e++;
    	w = k + o[d].x - 1;
    	chk[w] = e;
    	while(w > 1) {
    		if(chk[w>>1] < chk[w]) chk[w>>1] = chk[w];
    		w >>= 1;
    	}
        if (o[d].y > m) {
        	tmp = o[d].y - m;
        	st = k;
        	ed = k + tmp - 1;
        	max2 = 0;
        	while(1) {
        		if(max2 < chk[st]) max2 = chk[st];
        		if(max2 < chk[ed]) max2 = chk[ed];
        		if(st == ed) break;
        		if(st&1) st++;
        		if(!(ed&1)) ed--;
        		if(st > ed) break;
        		st >>= 1;
        		ed >>= 1;
        	}

        	if(max2 != 0) if(min1 > e - max2 + 1) min1 = e - max2 + 1;
        }
        d = moth[d];
    }
    d = x;
    while(d) {
    	w = k + o[d].x - 1;
    	chk[w] = 0;
    	while(w > 1) {
    		chk[w>>1] = 0;
    		w >>= 1;
    	}
    	d = moth[d];
    }
}
int main() {
    int i;
    int maxy;
    int d;
    int nx, ny, nnum;
    int st, ed;
    scanf("%d %d", &m, &n);
    for (k = 1; k < m * 2; k <<= 1);
    for (i = 1; i <= n; i++) {
        moth[i] = -1;
        scanf("%d %d", &o[i].x, &o[i].y);
        if (o[i].x > o[i].y) o[i].y += m;
        else {
            o[i].x += m;
            o[i].y += m;
        }
        o[i].y++;
    }
    std::sort(o + 1, o + n + 1, fsort);
    maxy = o[1].y;
    if (o[1].x > m && o[1].y > m) {
        o[1].x -= m;
        o[1].y -= m;
    }
    for (i = 2; i <= n; i++) {
        if (o[i].y <= maxy) o[i].x = 0x7fffffff;
        else maxy = o[i].y;

        if (o[i].x != 0x7fffffff && o[i].x > m && o[i].y > m) {
            o[i].x -= m;
            o[i].y -= m;
        }
    }
    std::sort(o + 1, o + n + 1, fsort);
    for (i = 1; i <= n; i++) {
        if(o[i].x == 0x7fffffff) break;
        o[i].num = i;

        d = k + o[i].x - 1;
        tree[d].x = o[i].x;
        tree[d].y = o[i].y;
        tree[d].num = o[i].num;
        while (d > 1) {
            if (tree[d / 2].y < tree[d].y) tree[d / 2] = tree[d];
            d /= 2;
        }
    }
    for (i = 1; i <= n; i++) {
        if (o[i].x == 0x7fffffff) break;
        if (moth[i] != -1) continue;
        nx = o[i].x;
        ny = o[i].y;
        nnum = o[i].num;
        while (1) {
            max1.num = 0;
            max1.x = 0;
            max1.y = 0;

            st = k + nx;
            ed = k + ny - 1;
            while (1) {
                if (max1.y < tree[st].y) max1 = tree[st];
                if (max1.y < tree[ed].y) max1 = tree[ed];
                if (st == ed) break;
                if (st & 1) st++;
                if (!(ed & 1)) ed--;
                if (st > ed) break;
                st /= 2;
                ed /= 2;
            }

            if (max1.num == 0) {
                moth[nnum] = 0;
                break;
            }
            son[max1.num]++;
            moth[nnum] = max1.num;
            if (moth[max1.num] != -1) break;
            nx = max1.x;
            ny = max1.y;
            nnum = max1.num;
        }
    }
    for (i = 1; i <= n; i++) {
        if (o[i].x == 0x7fffffff) break;
        if (son[i]) continue;
        _find(i);
    }
    if(min1 != 0x7fffffff) printf("%d", min1);
    else printf("impossible");
    return 0;
}

baekjoon 9년 전 1

저 문제는 공식 데이터를 사용합니다. live archive는 직접 만든 데이터를 사용하고요. (공식 데이터도 사용하는지는 잘 모르겠습니다)

문제에 따라서 추가로 만든 데이터를 사용하는 경우도 있는데, 바로 이런 경우입니다.

shjgkwo 9년 전 0

제가 실언을 했네요...

데이터가 부족한게 아니라.. 그 사이트 입출력 하는 방법을 몰라서 WA가 나오는 거 였어요 ㅠㅠ

죄송해요 ㅠㅠ

baekjoon 9년 전 0

아하 그렇군요

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

문제

문제

출처

ICPC

채점 컴퓨터가 리눅스가 아닌가요?

shjgkwo 9년 전 0

pichulia 9년 전 1

shjgkwo 9년 전 0

shjgkwo 9년 전 0

baekjoon 9년 전 1

shjgkwo 9년 전 0

baekjoon 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말