oj.uz

Submission #67092

# Submission time Handle Problem Language Result Execution time Memory
67092 2018-08-13T10:35:11 Z osmanorhan DEL13 (info1cup18_del13) C++17
100 / 100
 23 ms 4412 KB 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <climits>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cassert>
#include <vector>
#define all(x) x.begin() , x.end()
#define fi first
#define se second
#define pb push_back
#define umax( x , y ) x = max( x , (y) )
#define umin( x , y ) x = min( x , (y) )
#define For( i , a ) for(int i=1;i<=a;i++)
#define ort (b+s)/2
#define y2 asrwjaelkf
#define y1 asseopirwjaelkf
#define set multiset

using namespace std;

typedef long long Lint;
typedef double db;
typedef pair<int,int> ii;
typedef pair<int,char> ic;
typedef pair<db,db> dd;
typedef pair<int,ii> iii;
typedef pair<ii,ii> i4;

const int maxn = 100020;
const int maxm = 1000020;
const int MOd = 998244353;

int a, b;
int ar[maxn], loc[maxn];
int dn[maxn][3], go[maxn][3];

bool f( int n, int x ) {
	if( n == a+2 ) {
		if( x == 0 ) return 1;
		return 0;
	}
	int &ret = dn[n][x];
	if( ret != -1 ) return ret;
	ret = 0;
	//printf("asd %d %d ->> %d\n",n,x,ret);
	if( !(x == 0 && ar[n] > 0) && ar[n] >= x && (ar[n]-x)%2 == 0 && f( n+1, 0 ) ) {
		go[n][x] = 0;
		return ret = 1;
	}
	if( ar[n] >= x+1 && (ar[n]-(x+1))%2 == 0 && f( n+1, 1 ) ) {
		go[n][x] = 1;
		return ret = 1;
	}
	if( ar[n] >= x+2 && (ar[n]-(x+2))%2 == 0 && f( n+1, 2 ) ) {
		go[n][x] = 2;
		return ret = 1;
	}
	return ret = 0;
}

void solve(  ) {

	scanf("%d %d",&b,&a);
	for(int i=1;i<=a;i++) scanf("%d",&loc[i]);
	sort( loc+1, loc+1+a );
	loc[a+1] = b+1;
	loc[0] = 0;
	for(int i=1;i<=a+1;i++) {
		ar[i] = loc[i]-loc[i-1] - 1;
		//printf("----- %d\n",ar[i]);
	} 
	for(int i=0;i<=a+2;i++)
		dn[i][0] = dn[i][1] = dn[i][2] = -1;
	if( f( 1, 0 ) ) {
		printf("%d\n",(b-a)/2);
		int n = 1, x = 0;
		vector<int> last;
		while( n < a+2 ) {
			int h = ar[n] - x - go[n][x];
			int l = loc[n-1] + 2;
			assert( h % 2 == 0 );
			while( h > 0 ) {
				printf("%d ",l);
				h -= 2;
				l += 2;
			}
			h += go[n][x];
			while( h ) {
				last.pb( loc[n] );
				h--;
			}

			x = go[n][x];
			n++;
		}
		for(int i=0;i<last.size();i++) printf("%d ",last[i]);
		printf("\n");
	} else printf("-1\n");
}

int main() {

    //freopen("asd.in","r",stdin);
    //freopen("output17.txt","w",stdout);

	int n;
	scanf("%d",&n);
	while( n-- ) solve();

	return 0;
}

Compilation message

del13.cpp: In function 'bool f(int, int)':
del13.cpp:56:14: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   return ret = 1;
          ~~~~^~~
del13.cpp:60:14: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   return ret = 1;
          ~~~~^~~
del13.cpp:64:14: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   return ret = 1;
          ~~~~^~~
del13.cpp:66:13: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  return ret = 0;
         ~~~~^~~
del13.cpp: In function 'void solve()':
del13.cpp:104:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<last.size();i++) printf("%d ",last[i]);
               ~^~~~~~~~~~~~
del13.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&b,&a);
  ~~~~~^~~~~~~~~~~~~~~
del13.cpp:72:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=a;i++) scanf("%d",&loc[i]);
                        ~~~~~^~~~~~~~~~~~~~
del13.cpp: In function 'int main()':
del13.cpp:115:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 12 ms 460 KB Output is correct
4 Correct 10 ms 588 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 616 KB Output is correct
2 Correct 4 ms 624 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 12 ms 460 KB Output is correct
4 Correct 10 ms 588 KB Output is correct
5 Correct 3 ms 624 KB Output is correct
6 Correct 3 ms 624 KB Output is correct
7 Correct 4 ms 680 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 12 ms 460 KB Output is correct
4 Correct 10 ms 588 KB Output is correct
5 Correct 3 ms 624 KB Output is correct
6 Correct 3 ms 624 KB Output is correct
7 Correct 4 ms 680 KB Output is correct
8 Correct 21 ms 1072 KB Output is correct
9 Correct 23 ms 2096 KB Output is correct
10 Correct 20 ms 2368 KB Output is correct
11 Correct 22 ms 4412 KB Output is correct