oj.uz

Submission #67730

# Submission time Handle Problem Language Result Execution time Memory
67730 2018-08-15T09:17:55 Z MrTEK Permutation Recovery (info1cup17_permutation) C++14
25 / 100
 38 ms 440 KB 
#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 = 705;
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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 10 ms 376 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 10 ms 376 KB Output is correct
3 Incorrect 38 ms 440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 10 ms 376 KB Output is correct
3 Incorrect 38 ms 440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 10 ms 376 KB Output is correct
3 Incorrect 38 ms 440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 10 ms 376 KB Output is correct
3 Incorrect 38 ms 440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 10 ms 376 KB Output is correct
3 Incorrect 38 ms 440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 10 ms 376 KB Output is correct
3 Incorrect 38 ms 440 KB Output isn't correct
4 Halted 0 ms 0 KB -