Submission #67496

#	Time	Username	Problem	Language	Result	Execution time	Memory
67496		MrTEK	DEL13 (info1cup18_del13)	C++14	0 / 100	30 ms	6176 KiB

del13

#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 isc+isc
#define right isc+isc+1
#define mid (l+r)/2
#define FAfi_IO ios_base::sync_with_fidio(false);
#define escl '\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 = 1e4 + 5;
const int SQ = 350;
const int MOD = 998244353;

typedef long long int lli;
typedef pair<int,int> pii;

int t,a,b,n,ar[N],sz[N],loc[N],dp[N][3];
vector <pii> v;
vector <int> wr1,wr2;

int f(int cur,int lst) {
	if (dp[cur][lst] != -1) return dp[cur][lst]; 
	int val = ar[cur] - lst;
	if (val < 0)return dp[cur][lst] = 0;
	if (cur == n) {
		if(val == 0 || (lst > 0 && val % 2 == 0) ) return dp[cur][lst] = 1;
		return dp[cur][lst] = 0;
	}
	if (val == 0) return dp[cur][lst] = f(cur + 1 ,0);
	if (val % 2 == 0) return dp[cur][lst] = f(cur + 1,2) | (lst ? f(cur + 1,0) : 0);
	return dp[cur][lst] = f(cur + 1,1);
}

void clear() {
	wr1.clear();
	wr2.clear();
	for (int i = 0 ; i <= n ; i++) sz[i] = 0;
	for (int i = 0 ; i <= n ; i++) for (int j = 0 ; j < 3 ; j++) dp[i][j] = -1;
}

void find_path(int cur,int lst) {
	v.pb(mp(cur,lst));
	int val = ar[cur] - lst;
	if (cur == n) return;
	if (val == 0) {
		find_path(cur + 1,0);
		return ;
	}
	if (val % 2 == 0) {
		if (dp[cur + 1][2] == 1) find_path(cur + 1,2);
		else find_path(cur + 1,0);
	}
	else {
		find_path(cur + 1,1);
	}
}

int main() {

	scanf("%d",&t);
	while(t--) {
		scanf("%d %d",&a,&b);
		int last = 0;
		loc[0] = 1;
		for (int i = 1 ; i <= b ; i++) {
			int val;
			scanf("%d",&val);
			loc[i] = val;
			ar[i] = val - last - 1;
			last = val;
		}
		d1(loc[1]);
		ar[n = b + 1] = a - last;
		loc[n] = a;

		bool flag = true;

		for (int i = 1 ; i <= n ; i++) {
			if (ar[i] < 0) {
				flag = false;
			}
		}
		clear();		
		if (flag && f(1,0)) {
			v.clear();
			find_path(1,0);
			for (int i = 0 ; i < len(v) ; i++) {
				int cur = v[i].fi, lst = v[i].sc;
				if (lst) {
					for (int j = 1 ; j <= lst ; j++) wr2.pb(loc[cur - 1]);
					sz[cur] += lst;
					sz[cur - 1] += lst;
				}
			}
			for (int i = 1 ; i <= n ; i++) {
				int l = loc[i - 1] + 1, r = loc[i] - 1;
				// d2(i,sz[i]);
				// d2(l,r);
				for (int j = l + 1 ; j < r ; j += 2) wr1.pb(j);
			}
			for (auto x : wr1) printf("%d ",x);
			for (auto x : wr2) printf("%d ",x);
			puts("");
		} else {
			printf("-1\n");
			continue;
		}
	}

	return 0;
}

Compilation message (stderr)

del13.cpp: In function 'int main()':
del13.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&t);
  ~~~~~^~~~~~~~~
del13.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a,&b);
   ~~~~~^~~~~~~~~~~~~~~
del13.cpp:82:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&val);
    ~~~~~^~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 25
• Subtask 5: 0 / 30