Submission #1832839


Source Code Expand

#include <bits/stdc++.h>
#define long long long
#define up(i,a,b) for (int i=a; i<=b; i++)
#define down(i,a,b) for (int i=a; i>=b; i--)
#define endl '\n'
#define X first
#define Y second
#define II pair<int, int>
#define III pair<int, pair<int, int> >
#define debug(X) cerr<< #X << " = " <<X << endl
#define debug2(X,Y) cerr<< #X << " = " <<X << ","<<#Y<<" = "<<Y<<endl
#define show(X,a,b) {cerr << #X << " = "; up(__,a,b) cerr << X[__] << ' '; cerr << endl;}
#define gc getchar
#define pc putchar
using namespace std;

inline void read(int &x)
{
    register int c = gc();
    x = 0;
    int neg = 0;
    for (;((c<48 || c>57) && c != '-') ;c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}
inline void writeln(int x){

         char buffor[21];
         register int i=0;
         int neg=0; if (x<0) {neg=1; x= -x;}
         do{
               buffor[i++]=(x%10)+'0';
               x/=10;
            } while(x);
           i--;
           if (neg) pc('-');
           while(i>=0) pc(buffor[i--]);
           pc('\n');
       }
const int N= 510;
int n;
int a[N*N];
int pos[N], List[N];
int em[N];
vector<int> Move;
void input()
{
    cin>>n;
    up(i,1,n) cin>>pos[i], a[pos[i]]= i;
}
bool bypos(int a, int b)
{
	return pos[a]< pos[b];
}
void solve()
{
	up(i,1,n) List[i]= i;
    sort(List+1, List+1+n, bypos);// val List[1] have the minimum pos

    up(i,1,n)
    {
		int val= List[i]; Move.clear(); //debug(i); debug2(val, pos[val]);
		int cnt0= 0;
		up(j,1,pos[val]-1)
		 if (a[j]== 0)
		 {
		 	if (cnt0== val-1) break;
		 	em[++cnt0]= j;
		 }

        if (cnt0== val- 1) up(j,1,val-1) a[em[j]]= val;
        else
		{
            up(j,1,pos[val]-1)
            {
                if (a[j]!=0 and j> pos[a[j]] )
				{
					em[++cnt0]= j; Move.push_back(a[j]);
				}
                if (cnt0== val-1) break;
            }
            if (cnt0< val-1) { cout<<"No"; return; }
            up(j,1,val-1) a[em[j]]= val;//fill the left
            int cur= pos[val]+1;
            for (auto u: Move)//push the Move to the right
			{
				while (cur<=n*n and a[cur]!=0) cur++;
				if (cur== n*n+1) { cout<<"No"; return; }
				a[cur]= u;
			}
		}

		int cur= pos[val]+1;
        up(j,val+1,n)
        {
        	while (cur<= n*n and a[cur]!=0) cur++;
        	if (cur== n*n+1) {cout<<"No"; return; }
        	a[cur]= val;
        }

    }

    cout<<"Yes"<<endl;
    up(i,1,n*n) cout<<a[i]<<" ";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);// don't use when interactive

    #ifdef I_Love_Pork
    #define TASK "agc008_d"
    freopen(TASK".inp","r",stdin);
    freopen(TASK".out","w",stdout);
	  #endif

    input();
    solve();

    return 0;
}

Submission Info

Submission Time
Task D - K-th K
User I_Love_Pork
Language C++14 (GCC 5.4.1)
Score 800
Code Size 2870 Byte
Status AC
Exec Time 128 ms
Memory 2176 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 800 / 800
Status
AC × 2
AC × 49
Set Name Test Cases
Sample 0_00.txt, 0_01.txt
All 0_00.txt, 0_01.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt
Case Name Status Exec Time Memory
0_00.txt AC 1 ms 256 KB
0_01.txt AC 1 ms 256 KB
1_00.txt AC 1 ms 256 KB
1_01.txt AC 114 ms 2176 KB
1_02.txt AC 33 ms 2176 KB
1_03.txt AC 69 ms 2176 KB
1_04.txt AC 60 ms 2176 KB
1_05.txt AC 128 ms 2176 KB
1_06.txt AC 47 ms 2176 KB
1_07.txt AC 72 ms 2176 KB
1_08.txt AC 60 ms 2176 KB
1_09.txt AC 1 ms 256 KB
1_10.txt AC 1 ms 256 KB
1_11.txt AC 1 ms 256 KB
1_12.txt AC 1 ms 256 KB
1_13.txt AC 1 ms 256 KB
1_14.txt AC 1 ms 256 KB
1_15.txt AC 58 ms 1536 KB
1_16.txt AC 14 ms 896 KB
1_17.txt AC 44 ms 1152 KB
1_18.txt AC 92 ms 1920 KB
1_19.txt AC 53 ms 2048 KB
1_20.txt AC 36 ms 1664 KB
1_21.txt AC 48 ms 2048 KB
1_22.txt AC 63 ms 1792 KB
1_23.txt AC 24 ms 1024 KB
1_24.txt AC 38 ms 2048 KB
1_25.txt AC 34 ms 1664 KB
1_26.txt AC 19 ms 1024 KB
1_27.txt AC 25 ms 896 KB
1_28.txt AC 6 ms 768 KB
1_29.txt AC 33 ms 1280 KB
1_30.txt AC 63 ms 1920 KB
1_31.txt AC 65 ms 2048 KB
1_32.txt AC 3 ms 640 KB
1_33.txt AC 103 ms 2048 KB
1_34.txt AC 2 ms 768 KB
1_35.txt AC 16 ms 896 KB
1_36.txt AC 77 ms 2048 KB
1_37.txt AC 59 ms 1920 KB
1_38.txt AC 93 ms 2048 KB
1_39.txt AC 5 ms 768 KB
1_40.txt AC 15 ms 1024 KB
1_41.txt AC 25 ms 1280 KB
1_42.txt AC 31 ms 1408 KB
1_43.txt AC 88 ms 1920 KB
1_44.txt AC 2 ms 640 KB
1_45.txt AC 2 ms 640 KB
1_46.txt AC 15 ms 768 KB