結果
問題 | No.270 next_permutation (1) |
ユーザー | ciel |
提出日時 | 2015-08-23 03:53:18 |
言語 | C90 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 26 ms / 2,000 ms |
コード長 | 1,040 bytes |
コンパイル時間 | 606 ms |
コンパイル使用メモリ | 25,840 KB |
実行使用メモリ | 4,380 KB |
最終ジャッジ日時 | 2023-08-23 06:59:37 |
合計ジャッジ時間 | 1,501 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 0 ms
4,376 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,376 KB |
testcase_06 | AC | 1 ms
4,376 KB |
testcase_07 | AC | 1 ms
4,380 KB |
testcase_08 | AC | 1 ms
4,376 KB |
testcase_09 | AC | 3 ms
4,376 KB |
testcase_10 | AC | 25 ms
4,380 KB |
testcase_11 | AC | 26 ms
4,380 KB |
testcase_12 | AC | 26 ms
4,380 KB |
testcase_13 | AC | 25 ms
4,380 KB |
testcase_14 | AC | 24 ms
4,380 KB |
ソースコード
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> int *B; long long R,S; void my_reverse(int *a,int start,int size){ int end=start+size-1; for(;start<end;start++){ S-=abs(a[start]-B[start]); S-=abs(a[end]-B[end]); int z=a[start];a[start]=a[end];a[end]=z; S+=abs(a[start]-B[start]); S+=abs(a[end]-B[end]); end--; } } bool my_next_permutation(int *a,int n,int size){ if(n<0||size<n)return false; int i; //my_reverse(a,n,size-n); for(i=size-2;i>=0;i--)if(a[i]<a[i+1])break; if(i<0){ my_reverse(a,0,size); return false; } int k=i; for(i=size-1;i>=k+1;i--)if(a[k]<a[i])break; int l=i; S-=abs(a[k]-B[k]); S-=abs(a[l]-B[l]); int z=a[k];a[k]=a[l];a[l]=z; S+=abs(a[k]-B[k]); S+=abs(a[l]-B[l]); my_reverse(a,k+1,size-(k+1)); return true; } int main(){ int N,K,i; scanf("%d%d",&N,&K); int *A=(int*)malloc(4*N); B=(int*)malloc(4*N); for(i=0;i<N;i++)scanf("%d",A+i); for(i=0;i<N;i++)scanf("%d",B+i); for(i=0;i<N;i++)S+=abs(A[i]-B[i]); for(;K--;)R+=S,my_next_permutation(A,N,N); printf("%lld\n",R); }