Submission #486456


Source Code Expand

Copy
#include <bits/stdc++.h>

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <sstream>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>



#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define iter(a) __typeof(a.begin())
#define FOR(it,a) for(iter(a)it=a.begin();it!=a.end();++it)
#define F first
#define S second
#define SZ(a) (int)((a).size())
#define sz(a) SZ(a)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ALL(a) (a).begin(),(a).end()
using namespace std;

typedef long long ll;
typedef pair<int,int> PI;
typedef unsigned long long ull;

#ifdef ONLINE_JUDGE
#define PR(...) (void(0))
#else
#define PR(...) do{cerr << "line : " << __LINE__ << ", " << endl; pr(#__VA_ARGS__, __VA_ARGS__);}while(0)
template<class T>
void pr(const string& name, T t){
  cerr << name << ": " << t << endl;
}
template<typename T, typename ... Types>
void pr(const string& names, T t, Types ... rest) {
  auto p = names.find(',');
  cerr << names.substr(0, p) << ": " << t << ", ";
  pr(string(names, p + 1), rest ...);
}
#endif

template<class T,class U> ostream& operator<< (ostream& o, const pair<T,U>& v){return o << "(" << v.F << ", " << v.S << ")";}
template<class T> ostream& operator<< (ostream& o, const vector<T>& v){o << "{";rep(i,SZ(v)) o << (i?", ":"") << v[i];return o << "}";}
template<class T,class U> ostream& operator<< (ostream& o, const map<T,U>& v){o << "{";for(const auto& e : v) o << e << ", ";return o << "}";}
template<class T,class U> ostream& operator<< (ostream& o, const unordered_map<T,U>& v){o << "{";for(const auto& e : v) o << e << ", ";return o << "}";}
template<class T> ostream& operator<< (ostream& o, const set<T>& v){o << "{";for(const auto& e : v) o << e << ", ";return o << "}";}
template<class T> string to_s(const T& v){ostringstream is;is << v;return is.str();}

const int dx[]={0,1,0,-1,1,1,-1,-1,0};
const int dy[]={1,0,-1,0,-1,1,1,-1,0};

#define endl '\n'

int in[1000];

set<vector<char> > app[1000];

int main(int argc, char *argv[])
{
  int w, h;

  cin >> w >> h;
  if(h > 100) return 0;
  
  rep(i, h) cin >> in[i];
  
  vector<char> go(w);
  rep(i, w){
    int t;
    cin >> t;
    go[i] = t;
  }
  
  priority_queue<pair<int, pair<int, vector<char> > > > q;

  vector<char> st;
  rep(i, w) st.pb(i);
  q.push(mp(0,mp(0,st)));

  while(!q.empty()){
    int cc = -q.top().F;
    int ne = q.top().S.F;
    auto cv = q.top().S.S;
    q.pop();
    if(app[ne].count(cv)) continue;
    app[ne].insert(cv);
    // PR(cc, ne, cv);
    if(ne == h && cv == go){
      cout << cc << endl;
      return 0;
    }
    
    rep(i, w - 1){
      swap(cv[i], cv[i + 1]);
      if(app[ne].count(cv) == 0)
        q.push(mp(-cc-1, mp(ne, cv)));
      swap(cv[i], cv[i + 1]);
    }
    
    if(ne < h){
      swap(cv[in[ne]], cv[in[ne] + 1]);
      q.push(mp(-cc, mp(ne + 1, cv)));
    }
  }
}

Submission Info

Submission Time
Task C - 天下一不正
User atetubou
Language C++11 (GCC 4.9.2)
Score 0
Code Size 3040 Byte
Status WA
Exec Time 2042 ms
Memory 77216 KB

Judge Result

Set Name small All
Score / Max Score 0 / 45 0 / 105
Status
AC × 35
TLE × 7
AC × 35
WA × 37
TLE × 7
Set Name Test Cases
small 00_sample_1.txt, 00_sample_2.txt, 01_manual00.txt, 01_manual01.txt, 01_manual02.txt, 01_manual03.txt, 01_manual04.txt, 05_small100.txt, 05_small101.txt, 05_small102.txt, 05_small103.txt, 05_small104.txt, 05_small105.txt, 05_small106.txt, 05_small107.txt, 05_small108.txt, 05_small109.txt, 05_small110.txt, 05_small111.txt, 05_small112.txt, 05_small113.txt, 05_small114.txt, 05_small115.txt, 05_small116.txt, 05_small117.txt, 05_small118.txt, 05_small119.txt, 05_small120.txt, 05_small121.txt, 05_small122.txt, 05_small123.txt, 05_small124.txt, 05_small125.txt, 05_small126.txt, 05_small127.txt, 05_small128.txt, 05_small129.txt, 05_small130.txt, 05_small131.txt, 05_small132.txt, 05_small133.txt, 05_small134.txt
All 00_sample_1.txt, 00_sample_2.txt, 01_manual00.txt, 01_manual01.txt, 01_manual02.txt, 01_manual03.txt, 01_manual04.txt, 05_small100.txt, 05_small101.txt, 05_small102.txt, 05_small103.txt, 05_small104.txt, 05_small105.txt, 05_small106.txt, 05_small107.txt, 05_small108.txt, 05_small109.txt, 05_small110.txt, 05_small111.txt, 05_small112.txt, 05_small113.txt, 05_small114.txt, 05_small115.txt, 05_small116.txt, 05_small117.txt, 05_small118.txt, 05_small119.txt, 05_small120.txt, 05_small121.txt, 05_small122.txt, 05_small123.txt, 05_small124.txt, 05_small125.txt, 05_small126.txt, 05_small127.txt, 05_small128.txt, 05_small129.txt, 05_small130.txt, 05_small131.txt, 05_small132.txt, 05_small133.txt, 05_small134.txt, 10_large100.txt, 10_large101.txt, 10_large102.txt, 10_large103.txt, 10_large104.txt, 10_large105.txt, 10_large106.txt, 10_large107.txt, 10_large108.txt, 10_large109.txt, 10_large110.txt, 10_large111.txt, 10_large112.txt, 10_large113.txt, 10_large114.txt, 10_large115.txt, 10_large116.txt, 10_large117.txt, 10_large118.txt, 10_large119.txt, 10_large120.txt, 10_large121.txt, 10_large122.txt, 10_large123.txt, 10_large124.txt, 10_large125.txt, 10_large126.txt, 10_large127.txt, 10_large128.txt, 10_large129.txt, 10_large130.txt, 10_large131.txt, 10_large132.txt, 10_large133.txt, 10_large134.txt, 10_large135.txt, 11_manual00.txt
Case Name Status Exec Time Memory
00_sample_1.txt AC 29 ms 920 KB
00_sample_2.txt AC 23 ms 844 KB
01_manual00.txt AC 23 ms 928 KB
01_manual01.txt AC 23 ms 924 KB
01_manual02.txt AC 45 ms 1316 KB
01_manual03.txt AC 196 ms 4156 KB
01_manual04.txt TLE 2039 ms 44916 KB
05_small100.txt AC 26 ms 736 KB
05_small101.txt AC 23 ms 924 KB
05_small102.txt AC 23 ms 928 KB
05_small103.txt AC 24 ms 1052 KB
05_small104.txt AC 68 ms 2292 KB
05_small105.txt AC 24 ms 932 KB
05_small106.txt AC 26 ms 1060 KB
05_small107.txt AC 25 ms 1184 KB
05_small108.txt AC 59 ms 4024 KB
05_small109.txt AC 453 ms 36140 KB
05_small110.txt AC 175 ms 10804 KB
05_small111.txt AC 67 ms 3260 KB
05_small112.txt AC 26 ms 808 KB
05_small113.txt AC 27 ms 928 KB
05_small114.txt AC 28 ms 1300 KB
05_small115.txt AC 64 ms 5296 KB
05_small116.txt AC 111 ms 9272 KB
05_small117.txt AC 158 ms 4788 KB
05_small118.txt AC 47 ms 3000 KB
05_small119.txt AC 602 ms 15016 KB
05_small120.txt AC 739 ms 38700 KB
05_small121.txt AC 400 ms 24872 KB
05_small122.txt AC 1680 ms 39216 KB
05_small123.txt TLE 2037 ms 44840 KB
05_small124.txt TLE 2039 ms 47072 KB
05_small125.txt AC 488 ms 36008 KB
05_small126.txt TLE 2042 ms 77216 KB
05_small127.txt AC 1562 ms 45352 KB
05_small128.txt AC 1238 ms 52392 KB
05_small129.txt TLE 2038 ms 45228 KB
05_small130.txt TLE 2041 ms 44544 KB
05_small131.txt TLE 2039 ms 46612 KB
05_small132.txt AC 1358 ms 56612 KB
05_small133.txt AC 1201 ms 50468 KB
05_small134.txt AC 1469 ms 44080 KB
10_large100.txt WA 25 ms 924 KB
10_large101.txt WA 25 ms 792 KB
10_large102.txt WA 26 ms 916 KB
10_large103.txt WA 26 ms 924 KB
10_large104.txt WA 26 ms 792 KB
10_large105.txt WA 25 ms 800 KB
10_large106.txt WA 25 ms 932 KB
10_large107.txt WA 26 ms 792 KB
10_large108.txt WA 25 ms 928 KB
10_large109.txt WA 26 ms 844 KB
10_large110.txt WA 25 ms 932 KB
10_large111.txt WA 24 ms 920 KB
10_large112.txt WA 24 ms 924 KB
10_large113.txt WA 25 ms 920 KB
10_large114.txt WA 26 ms 804 KB
10_large115.txt WA 25 ms 804 KB
10_large116.txt WA 26 ms 804 KB
10_large117.txt WA 26 ms 800 KB
10_large118.txt WA 26 ms 924 KB
10_large119.txt WA 26 ms 804 KB
10_large120.txt WA 24 ms 924 KB
10_large121.txt WA 25 ms 928 KB
10_large122.txt WA 24 ms 920 KB
10_large123.txt WA 23 ms 796 KB
10_large124.txt WA 25 ms 724 KB
10_large125.txt WA 23 ms 932 KB
10_large126.txt WA 25 ms 728 KB
10_large127.txt WA 23 ms 808 KB
10_large128.txt WA 26 ms 800 KB
10_large129.txt WA 26 ms 920 KB
10_large130.txt WA 26 ms 916 KB
10_large131.txt WA 23 ms 796 KB
10_large132.txt WA 23 ms 924 KB
10_large133.txt WA 23 ms 924 KB
10_large134.txt WA 24 ms 924 KB
10_large135.txt WA 26 ms 800 KB
11_manual00.txt WA 25 ms 920 KB