Submission #489385


Source Code Expand

Copy
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }

typedef long long int lint;
typedef pair<int,int> pi;

namespace std{
	template<class S,class T>
	ostream &operator <<(ostream& out,const pair<S,T>& a){
		out<<'('<<a.fr<<','<<a.sc<<')';
		return out;
	}
}

const int INF=5e8;

int w,h;
vector<int> g[6000];

int ar[100005];

typedef vector<int> vi;
vector<vi> perm;

int dp[25][6000];

int type[100005];

int K,L;

vi swapPos[10][10];

int main(){
  cin>>w>>h;

  K=1;
  REP(i,w) K*=i+1;

  L=w*(w-1)/2+1;

  vi trg(w);
  REP(i,h) scanf("%d",&ar[i]);
  REP(i,w) scanf("%d",&trg[i]);

  vi tmp(w);
  REP(i,w) tmp[i]=i;
  do{
    perm.pb(tmp);
  }while(next_permutation(ALL(tmp)));

  vi cur(w);
  REP(i,w) cur[i]=i;

  type[h]=0;
  for(int i=h-1;i>=0;--i){
    int a=ar[i];
    swap(cur[a],cur[a+1]);
    type[i]=lower_bound(ALL(perm),cur)-perm.begin();
  }


  REP(i,h+1){
    int t=type[i];
    vi p=perm[t];

    REP(j,w-1){
      int a=p[j],b=p[j+1];
      if(a>b) swap(a,b);
      swapPos[a][b].pb(i);
    }
  }
  REP(j,w) REPN(j2,w,j+1) swapPos[j][j2].pb(INF);

  vi rev(w);
  REP(i,w) rev[cur[i]]=i;

  int initState=lower_bound(ALL(perm),rev)-perm.begin();

  REP(i,L) REP(j,K) dp[i][j]=INF;
  dp[0][initState]=0;

  REP(i,L) REP(j,K) if(dp[i][j]<INF){

    if(i+1<L) REP(s,w) REPN(t,w,s+1){
      int lb=*lower_bound(ALL(swapPos[s][t]),dp[i][j]);


      if(lb==INF) continue;

      vi p=perm[j];
      swap(p[s],p[t]);

      int id=lower_bound(ALL(perm),p)-perm.begin();

      chmin(dp[i+1][id],lb);
    }
  }

  int goal=lower_bound(ALL(perm),trg)-perm.begin();
  int res=INF;
  REP(i,L) if(dp[i][goal]<INF){
    res=i;
    break;
  }
  cout<<res<<endl;

	return 0;
}

Submission Info

Submission Time
Task C - 天下一不正
User hogloid
Language C++11 (GCC 4.9.2)
Score 150
Code Size 2469 Byte
Status
Exec Time 414 ms
Memory 6048 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:66:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   REP(i,h) scanf("%d",&ar[i]);
                              ^
./Main.cpp:67:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   REP(i,w) scanf("%d",&trg[i]);
                               ^

Judge Result

Set Name small All
Score / Max Score 45 / 45 105 / 105
Status
× 42
× 79
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 24 ms 1048 KB
00_sample_2.txt 26 ms 864 KB
01_manual00.txt 25 ms 928 KB
01_manual01.txt 25 ms 936 KB
01_manual02.txt 77 ms 1828 KB
01_manual03.txt 99 ms 1884 KB
01_manual04.txt 99 ms 1832 KB
05_small100.txt 26 ms 924 KB
05_small101.txt 24 ms 928 KB
05_small102.txt 25 ms 928 KB
05_small103.txt 36 ms 1172 KB
05_small104.txt 151 ms 1948 KB
05_small105.txt 26 ms 1052 KB
05_small106.txt 23 ms 1052 KB
05_small107.txt 28 ms 932 KB
05_small108.txt 44 ms 1184 KB
05_small109.txt 320 ms 1824 KB
05_small110.txt 318 ms 1948 KB
05_small111.txt 175 ms 1944 KB
05_small112.txt 26 ms 940 KB
05_small113.txt 27 ms 932 KB
05_small114.txt 25 ms 1008 KB
05_small115.txt 42 ms 1064 KB
05_small116.txt 322 ms 1836 KB
05_small117.txt 190 ms 1956 KB
05_small118.txt 286 ms 1824 KB
05_small119.txt 237 ms 1832 KB
05_small120.txt 290 ms 1952 KB
05_small121.txt 312 ms 1824 KB
05_small122.txt 100 ms 1824 KB
05_small123.txt 97 ms 1824 KB
05_small124.txt 111 ms 1940 KB
05_small125.txt 291 ms 1832 KB
05_small126.txt 306 ms 1828 KB
05_small127.txt 184 ms 1880 KB
05_small128.txt 295 ms 1828 KB
05_small129.txt 100 ms 1876 KB
05_small130.txt 96 ms 1932 KB
05_small131.txt 111 ms 1824 KB
05_small132.txt 320 ms 1880 KB
05_small133.txt 312 ms 1952 KB
05_small134.txt 185 ms 1832 KB
10_large100.txt 57 ms 2788 KB
10_large101.txt 61 ms 3000 KB
10_large102.txt 67 ms 3596 KB
10_large103.txt 96 ms 4612 KB
10_large104.txt 400 ms 5408 KB
10_large105.txt 57 ms 2952 KB
10_large106.txt 58 ms 3148 KB
10_large107.txt 67 ms 3600 KB
10_large108.txt 73 ms 4104 KB
10_large109.txt 92 ms 4492 KB
10_large110.txt 395 ms 5464 KB
10_large111.txt 394 ms 5332 KB
10_large112.txt 414 ms 5816 KB
10_large113.txt 145 ms 5376 KB
10_large114.txt 303 ms 6048 KB
10_large115.txt 158 ms 5320 KB
10_large116.txt 406 ms 5496 KB
10_large117.txt 406 ms 5752 KB
10_large118.txt 397 ms 5400 KB
10_large119.txt 397 ms 5412 KB
10_large120.txt 56 ms 2892 KB
10_large121.txt 58 ms 3032 KB
10_large122.txt 63 ms 3980 KB
10_large123.txt 69 ms 4100 KB
10_large124.txt 93 ms 4616 KB
10_large125.txt 337 ms 2204 KB
10_large126.txt 93 ms 4484 KB
10_large127.txt 396 ms 5412 KB
10_large128.txt 408 ms 5632 KB
10_large129.txt 149 ms 5376 KB
10_large130.txt 174 ms 5324 KB
10_large131.txt 164 ms 5520 KB
10_large132.txt 242 ms 5432 KB
10_large133.txt 403 ms 5828 KB
10_large134.txt 402 ms 5540 KB
10_large135.txt 391 ms 5152 KB
11_manual00.txt 147 ms 5368 KB