Submission #67729

#	Time	Username	Problem	Language	Result	Execution time	Memory
67729		MrTEK	Permutation Recovery (info1cup17_permutation)	C++14	25 / 100	47 ms	948 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define mp make_pair
#define pb push_back
#define len(a) (int)a.size()
#define fi first
#define sc second
#define d1(w) cerr<<#w<<":"<<w<<endl;
#define d2(w,c) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<endl;
#define d3(w,c,z) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<" "<<#z<<":"<<z<<endl;
#define left ind+ind
#define right ind+ind+1
#define mid (l+r)/2
#define FAST_IO ios_base::sync_with_stdio(false);
#define endl '\n'

typedef long long int ll;

const int maxn = 620;
const long long LINF = 1e18;
const int LOG = 31;
const int INF = 1e9;
const int N = 1e5 + 5;
const int M = 60;
const int SQ = 350;
const int MOD = 998244353;

typedef pair <int,int> pii;

int n,q[N],is[N],a[N],mark[N];

int main() {

	scanf("%d",&n);

	assert(n <= 700);

	for (int i = 1 ; i <= n ; i++) scanf("%d",&q[i]);
	a[1] = 1;
	is[1] = 1;
	for (int i = 2 ; i <= n ; i++) {
		int diff = q[i] - q[i - 1] - 1,cnt = 0,say = 0;
		vector <pair <int,pii> > v;
		memset(mark,0,sizeof mark); 
		for (int j = 1 ; j < i ; j++)
			v.pb(mp(a[j],mp(is[a[j]],j)));
		sort(v.begin(),v.end());
		// d1(diff);
		for (int j = 0 ; j < len(v) ;j++) {
			if (diff == 0) break;
			diff -= v[j].sc.fi;
			say++;
			cnt += v[j].sc.fi;
			mark[v[j].sc.sc] = 1;
		}
		// printf("%d\n--------\n",i);
		// for (int j = 1 ; j < i ; j++) printf("%d ",mark[i]);
		// puts("");
		for (int j = len(v) - 1; j >= 0 ; j--) {
			int x = v[j].sc.sc;
			if (mark[x] == 0) {
				is[a[x] + 1] = is[a[x]];
				a[x]++;
			}
		}
		a[i] = say + 1;
		is[a[i]] = cnt + 1;
		// for (int i = 1 ; i <= n ; i++) printf("%d ",a[i]);
		// puts("");
	}
	for (int i = 1 ; i <= n ; i++) {
		printf("%d ",a[i]);
	}
}

Compilation message (stderr)

permutation.cpp: In function 'int main()':
permutation.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
permutation.cpp:39:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1 ; i <= n ; i++) scanf("%d",&q[i]);
                                 ~~~~~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 0 / 18
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 7
• Subtask 7: 0 / 16
• Subtask 8: 0 / 6