글 읽기 - 답은 맞았는데, 혹시 제 풀이에 문제가 있을까요?

shjohw12 2년 전 0

이번 삼성 오후시험 응시했고 지금 작성한 코드와 똑같이(아마?) 풀었습니다. 근데 시험볼때는 샘플로 제공된 테스트 케이스 하나에서 1차이로 답이 다르게 나왔었습니다. 혹시 제 풀이에 문제점이 있는지 봐주시면 감사하겠습니다.

#include<bits/stdc++.h>
#define int ll
#define sz(x) int((x).size())
#define all(x) (x).begin(),(x).end()
#define x first
#define y second
using namespace std;
using ll = long long;
using pi = pair<int,int>;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int minf = 0xc0c0c0c0c0c0c0c0;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};


int A[55][55];
int Idx[55][55];

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n,m; cin>>n>>m;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) cin>>A[i][j];
    }

    list<int> li;

    for (int i=n/2, j=n/2, step=0, dir=1, idx=-1;; dir=(dir+1)%4) {
        if (dir&1) ++step;
        for (int tt=step; tt; tt--) {
            i += dx[dir], j += dy[dir];
            Idx[i][j] = ++idx;
            if (A[i][j]) li.push_back(A[i][j]);
            if (i==0 && j==0) break;
        }
        if (i==0 && j==0) break;
    }

    using pp = pair<list<int>::iterator,int>;

    int res = 0;

    while (m--) {
        int dir,len; cin>>dir>>len;
        if (dir==1) dir=0;
        else if (dir==3) dir=1;
        else if (dir==4) dir=3;

        vector<list<int>::iterator> ers;
        int i = n/2, j = n/2;

        while (len--) {
            i += dx[dir], j += dy[dir];
            if (sz(li) <= Idx[i][j]) break;
            auto it = li.begin();
            advance(it, Idx[i][j]);
            ers.push_back(it);
        }

        for (auto &it : ers) {
            li.erase(it);
        }

        auto it = li.begin();

        vector<pp> st;

        while (it != li.end()) {

            auto jt = next(it);
            int cnt = 1;
            for (; jt != li.end(); ++jt) {
                if (*it == *jt) {
                    ++cnt;
                }
                else break;
            }


            if (sz(st) && *st.back().x == *it) {
                st.back().y += cnt;
            }
            else {
                st.push_back(pp(it, cnt));
            }

            if (st.back().y >= 4) {
                res += *st.back().x * st.back().y;
                st.pop_back();
            }

            it = jt;
        }

        list<int> li_nxt;

        for (auto &[it, cnt] : st) {
            li_nxt.push_back(cnt);
            if (sz(li_nxt) == n*n - 1) break;
            li_nxt.push_back(*it);
            if (sz(li_nxt) == n*n - 1) break;
        }


        swap(li, li_nxt);
    }

    cout<<res<<'\n';

    return 0;
}

pichulia 2년 전 2

지금 보먼 4개가 모이자마자 터트리고있는데

그런 경우 틀립니다.

숫자들이 동시에 터진 뒤에 이동한다는 내용이 지문에 언급되있었을 것입니다. 해당 코드는 그대로 작성되지 않았고요.

답이 실제로 다르게 다오는 반례는 찾아봐야 하지겠만..실제 시험장에선 이런 예제가 있던게 아닐까요.

1 2 2 2 2 1 3 3 3 3 1 1 1 1
--> 
1 1

pichulia 2년 전 6

반례입니다.

정답은 97 입니다.

1
0 0 0 0 0 0 0 0
2 1 3 1 3 3 3 0
3 3 3 1 3 3 1 0
2 2 2 1 2 2 1 0
1 2 1 0 2 2 1 0
3 3 1 1 2 2 2 0
3 3 3 1 1 1 2 0
1 1 1 3 3 3 2 0
0 0 0 0 0 0 0 0
3

shjohw12 2년 전 0

헉 반례까지.. 정말 감사드립니다!!

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

문제

문제

출처

ICPC

답은 맞았는데, 혹시 제 풀이에 문제가 있을까요?

shjohw12 2년 전 0

pichulia 2년 전 2

pichulia 2년 전 6

shjohw12 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말