글 읽기 - 데이터 부족?

exqt 7년 전 0

5 2 4 10 7 9 8 1 6 3

를 넣으면 제 노트북에서도 엄청 오래 걸리고 ideone에서 tle(5초?) 가 납니다.

공식 풀이도 양방향 탐색인데 제 코드가 8ms 나오는것을 보면 문제가 있는것 같습니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <fstream>
#include <string>
#include <map>
#include <queue>
#include <utility>
#include <cstdio>
#include <cmath>
#include <iterator>
#include <set>
#include <bitset>
using namespace std;

#define in cin
#define out cout

#define REP(i,n) for(int i=0; i<n; i++)
#define REP2(i,s,e) for(int i=s; i<e; i++)
#define REPE(i,s,e) for(int i=s; i<=e; i++)
#define REPR(i,s,e) for(int i=s; i>=e; i--)

#define all(v) v.begin(), v.end()
#define pb push_back

#define ll long long
#define pii pair<int, int>

#define x first
#define y second
#define intINF 2147483647
#define llINF 9223372036854775807LL
#define MOD 1000000007

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    int n; in >> n;
    map<string, int> MP;

    string src = "";
    REP(i, n)
    {
        int t; in >> t; t--;
        src += char(t+'0');
    }

    string dest = "";
    REP(i, n) dest += (i+'0');

    MP[src] = 1;
    queue< string > Q;
    Q.push(src);

    int counter = 0;

    while(Q.size())
    {
        string here = Q.front(); Q.pop();
        //out << here << "\n";
        REP(i,n) REP2(j,i,n) REP2(k,j,n)
        {
            // 0 to i-1 a
            // i to j-1 b
            // j to k-1 c
            // k to n-1 d
            // c a d b
            string r = "";
            REP2(_,j,k) r += here[_];
            REP2(_,0,i) r += here[_];
            REP2(_,k,n) r += here[_];
            REP2(_,i,j) r += here[_];

            if(here == dest) {out << MP[here]-1 << "\n"; goto EX;}

            auto &mhere = MP[here];
            auto &mthere = MP[r];

            if(mthere == 0)
            {
                mthere = mhere + 1;
                Q.push(r);
            }
        }
    }

    EX:

    return 0;
}

baekjoon 7년 전 1

재채점했습니다.

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

문제

문제

출처

ICPC

데이터 부족?

exqt 7년 전 0

baekjoon 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말