Submission #1817268
Source Code Expand
/*#include<cstdio>
#include<algorithm>
using namespace std;
int w[101000];
int n;
int main(){
int i;
// freopen("/Users/joseunghyeon/Downloads/in (2)/eval_input.txt","r",stdin);
int TC, TT;
scanf("%d",&TC);
for(TT=1;TT<=TC;TT++){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&w[i]);
sort(w+1,w+n+1);
printf("Case #%d\n",TT);
if(w[n]-w[1]>1){
printf("No\n");
continue;
}
if(w[n]-w[1]==0){
if(w[1] <= n/2 || w[1] == n-1)printf("Yes\n");
else printf("No\n");
continue;
}
for(i=1;i<n;i++)if(w[i]!=w[i+1])break;
int t = i;
if(t + 1 <= w[n] && t + (n-t)/2 >= w[n])printf("Yes\n");
else printf("No\n");
}
}
*/
/*#include<cstdio>
#include<algorithm>
using namespace std;
int n, w[201000];
int main(){
char fp[200];
int T[2]={6,18};
freopen("/Users/joseunghyeon/Downloads/in (2)/eval_input.txt","w",stdout);
printf("%d\n",T[0]+T[1]);
for(int TTT = 0; TTT < 2; TTT++){
for(int TT=0;TT< T[TTT];TT++){
fprintf(stderr,"%d %d\n",TTT,TT);
sprintf(fp, "/Users/joseunghyeon/Downloads/in (2)/%d_%02d.txt", TTT, TT);
freopen(fp, "r",stdin);
int n, a;
scanf("%d",&n);
printf("%d\n",n);
for(int i=0;i<n;i++){
scanf("%d",&a);
printf("%d",a);
if(i!=n-1)printf(" ");
}
printf("\n");
}
}
return 0;
}
*/
/*#include<cstdio>
#include<algorithm>
using namespace std;
int n, w[201000];
int main(){
char fp[200];
int TC = 0;
int T[2]={6,18};
freopen("/Users/joseunghyeon/Downloads/out (2)/eval_output.txt","w",stdout);
for(int TTT = 0; TTT < 2; TTT++){
for(int TT=0;TT< T[TTT];TT++){
fprintf(stderr,"%d %d\n",TTT,TT);
sprintf(fp, "/Users/joseunghyeon/Downloads/out (2)/%d_%02d.txt", TTT, TT);
freopen(fp, "r",stdin);
char rr[10];
scanf("%s",rr);
printf("Case #%d\n%s\n",++TC,rr);
}
}
return 0;
}*/
/*
#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
map<vector<int>,int>Map;
vector<int> Do(vector<int>T){
vector<int>ret,T1,T2;
if(T.size()==1){
ret.push_back(T[0]+1);
return ret;
}
int i;
for(i=0;i<T.size()/2;i++){
T1.push_back(min(T[i*2],T[i*2+1]));
T2.push_back(max(T[i*2],T[i*2+1]));
}
vector<int>r1, r2;
r1 = Do(T1);
r2 = Do(T2);
for(i=0;i<r1.size();i++)ret.push_back(r1[i]);
for(i=0;i<r2.size();i++)ret.push_back(r2[i]);
return ret;
}
int main(){
int i, w[8];
vector<int>TP(8);
vector<int>res;
for(i=0;i<8;i++)w[i]=i;
do{
for(i=0;i<8;i++)TP[i]=w[i];
res = Do(TP);
Map[res] = 1;
}while(next_permutation(w,w+8));
for(auto &tp : Map){
for(i=0;i<8;i++)printf("%d ",tp.first[i]);
printf("\n");
}
}*/
#include<cstdio>
#include<algorithm>
using namespace std;
int n, w[201000], Loc[201000], G[201000];
struct point{
int x, num;
bool operator<(const point &p)const{
return x!=p.x?x<p.x:num<p.num;
}
}ord[210000];
void RTE(){
RTE();
RTE();
}
int main(){
int i, j;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&w[i]);
Loc[i] = i;
G[i] = i;
ord[i] = {w[i],i};
}
sort(ord+1,ord+n+1);
long long res = 0;
for(i=1;i<=n;i++){
int t = Loc[ord[i].num];
int M = 0, Mn = 2e9, xx = 0, U = -1;
for(j=1;j<=t;j++){
if(Mn >= max(0,M-ord[i].x)+(t-j)){
Mn = max(0,M-ord[i].x)+(t-j);
U = max(M, ord[i].x);
xx = j;
}
M = max(M, w[G[j]]);
}
w[ord[i].num] = U;
res += Mn;
for(j=t;j>xx;j--){
swap(G[j-1],G[j]);
swap(Loc[G[j-1]],Loc[G[j]]);
}
}
printf("%lld\n",res);
}
Submission Info
Submission Time
2017-11-30 11:33:10+0900
Task
B - Increment and Swap
User
ainta
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
4251 Byte
Status
WA
Exec Time
2104 ms
Memory
4096 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:144:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:146:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&w[i]);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
0 / 1500
Status
Set Name
Test Cases
Sample
example0.txt, example1.txt
All
000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, 050.txt, 051.txt, 052.txt, 053.txt, 054.txt, 055.txt, 056.txt, 057.txt, 058.txt, 059.txt, 060.txt, 061.txt, 062.txt, 063.txt, example0.txt, example1.txt
Case Name
Status
Exec Time
Memory
000.txt
TLE
2103 ms
4096 KB
001.txt
TLE
2103 ms
4096 KB
002.txt
TLE
2103 ms
4096 KB
003.txt
TLE
2103 ms
4096 KB
004.txt
TLE
2103 ms
4096 KB
005.txt
TLE
2103 ms
4096 KB
006.txt
TLE
2103 ms
4096 KB
007.txt
TLE
2103 ms
4096 KB
008.txt
TLE
2103 ms
4096 KB
009.txt
TLE
2103 ms
4096 KB
010.txt
TLE
2103 ms
4096 KB
011.txt
TLE
2103 ms
4096 KB
012.txt
TLE
2103 ms
4096 KB
013.txt
TLE
2103 ms
4096 KB
014.txt
TLE
2103 ms
4096 KB
015.txt
TLE
2103 ms
4096 KB
016.txt
TLE
2103 ms
4096 KB
017.txt
TLE
2104 ms
4096 KB
018.txt
TLE
2103 ms
4096 KB
019.txt
TLE
2104 ms
4096 KB
020.txt
TLE
2103 ms
4096 KB
021.txt
WA
612 ms
640 KB
022.txt
TLE
2103 ms
3840 KB
023.txt
TLE
2103 ms
2048 KB
024.txt
WA
1980 ms
896 KB
025.txt
TLE
2103 ms
2560 KB
026.txt
WA
943 ms
640 KB
027.txt
TLE
2103 ms
3072 KB
028.txt
TLE
2103 ms
1664 KB
029.txt
TLE
2103 ms
1664 KB
030.txt
TLE
2103 ms
1664 KB
031.txt
TLE
2103 ms
3072 KB
032.txt
TLE
2103 ms
2048 KB
033.txt
TLE
2103 ms
2048 KB
034.txt
TLE
2103 ms
3328 KB
035.txt
TLE
2103 ms
768 KB
036.txt
TLE
2103 ms
3712 KB
037.txt
TLE
2103 ms
2944 KB
038.txt
TLE
2103 ms
896 KB
039.txt
TLE
2103 ms
2304 KB
040.txt
TLE
2103 ms
2048 KB
041.txt
TLE
2103 ms
3584 KB
042.txt
TLE
2103 ms
4096 KB
043.txt
TLE
2103 ms
4096 KB
044.txt
TLE
2103 ms
4096 KB
045.txt
AC
1 ms
128 KB
046.txt
TLE
2104 ms
4096 KB
047.txt
TLE
2103 ms
4096 KB
048.txt
TLE
2103 ms
4096 KB
049.txt
TLE
2104 ms
4096 KB
050.txt
TLE
2103 ms
4096 KB
051.txt
TLE
2103 ms
4096 KB
052.txt
TLE
2103 ms
4096 KB
053.txt
TLE
2103 ms
4096 KB
054.txt
TLE
2103 ms
4096 KB
055.txt
TLE
2104 ms
4096 KB
056.txt
TLE
2103 ms
4096 KB
057.txt
TLE
2103 ms
4096 KB
058.txt
TLE
2104 ms
4096 KB
059.txt
TLE
2103 ms
4096 KB
060.txt
TLE
2103 ms
4096 KB
061.txt
TLE
2103 ms
4096 KB
062.txt
TLE
2103 ms
4096 KB
063.txt
TLE
2103 ms
4096 KB
example0.txt
AC
1 ms
128 KB
example1.txt
AC
1 ms
128 KB