Submission #283467

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
283467	2020-08-25T19:30:20 Z	kshitij_sodani	DEL13 (info1cup18_del13)	C++14	Compilation error	0 ms	0 KB

del13

//#pragma GCC optimize("Ofast,unroll-loops")//
//#pragma GCC target("fma,avx")//,avx2,fma")
//#pragma GCC optimization ("O3")


/*#pragma GCC optimization ("unroll-loops")
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
*/
#include <bits/stdc++.h>
using namespace std;
//typedef long long int;
#define mp make_pair
#define pb push_back
#define a first 
#define b second


int t;

int vis[200001];
int dp[200001][3];
int back[200001][3];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>t;
	while(t--){
		int n,q;
		cin>>n>>q;
		if(q==0){
			cout<<-1<<endl;
			continue;
		}
		for(int i=0;i<n;i++){
			vis[i]=0;
		}
		//vector<int> aa;
		set<int> ac;
		for(int i=0;i<q;i++){
			int bb;
			cin>>bb;
			bb--;
			vis[bb]=1;
			//aa.pb(bb);
			ac.insert(bb);
		}
		if(q==n){
			cout<<0<<endl;
			cout<<endl;
			continue;
		}
		vector<vector<deque<int>>> ss;
		int cot=0;
		int stt=0;
		for(int i=0;i<n;i++){
			if(vis[i]==0){
			//	cout<<i<<"::"<<endl;

				if(cot>=2 or stt==0){
					deque<int> tt;
					tt.pb(i);
					ss.pb({tt});
				}
				else if(cot==0){
					ss[ss.size()-1][ss[ss.size()-1].size()-1].pb(i);
				}
				else{
					deque<int> tt;
					tt.pb(i);
					ss[ss.size()-1].pb(tt);
				}
				stt=1;
				cot=0;
			}
			else{
				cot+=1;
			}
		}
		vector<int> ans;
		int ye=0;
	
		for(int i=0;i<ss.size();i++){
			for(int j=0;j<ss[i].size();j++){
				//cout<<j<<":";
				while(ss[i][j].size()>4){
					int aa=ss[i][j].back();
					ss[i][j].pop_back();
					int bb=ss[i][j].back();
					ss[i][j].pop_back();
					int cc=ss[i][j].back();
					ss[i][j].pop_back();
					ans.pb(bb);
					ss[i][j].pb(bb);
				}
			}
			//cout<<",,"<<endl;
			if(ss[i].size()==1){
				ye=1;
				break;
			}
			for(int j=0;j<ss[i].size();j++){
				dp[j][0]=0;
				dp[j][1]=0;
				dp[j][2]=0;

			}
			for(int j=1;j<=2;j++){
				if(ss[i][1].size()>=j and ss[i][0].size()>=j and ss[i][0].size()%2==j%2){
					dp[1][j]=1;
					back[1][j]=j;
				//	cout<<j<<"<"<<'\n';
				}
			}
			for(int j=2;j<ss[i].size();j++){
				for(int jj=0;jj<=min(2,ss[i][j].size());jj++){
					for(int ii=0;ii<=2;ii++){
						if(ii+jj==0){
							continue;
						}
						if(((int)((int)ss[i][j-1].size()))>=ii+jj){
							if(((int)(ss[i][j-1].size())-ii-jj)%2==0){
								if(dp[j-1][ii]==1){
									dp[j][jj]|=dp[j-1][ii];
									back[j][jj]=ii;
								//	cout<<jj<<",,"<<ii<<endl;
								}
							}
						}
					}
				}
			}
			ye=1;
		//	cout<<back[2][2]<<endl;
			for(int ko=ss[i].back().size();ko>0;ko-=2){
				if(dp[ss[i].size()-1][ko]){
					ye=0;
				//	cout<<ko<<"//"<<endl;
					vector<int> jj;
					jj.pb(ko);
					for(int ii=ss[i].size()-1;ii>0;ii--){
					//	cout<<ii<<".."<<jj.back()<<endl;
					//	cout<<back[ii][jj.back()]<<endl;
						int xo=back[ii][jj.back()];

						jj.pb(xo);	

					}
					reverse(jj.begin(),jj.end());
			/*		for(auto jo:jj){
						cout<<jo<<".";
					}+
					cout<<endl;*/
					vector<int> mm;
					for(int j=0;j<ss[i].size();j++){
						mm.pb(ss[i][j].size());
					}
					for(int j=0;j<ss[i].size();j++){
						int le=mm[j]-jj[j];
						if(j>0){
							if(j<(int)(ss[i].size())-1){
								le-=jj[j+1];
							}
						}
						/*if(le<0){
							while(true){
								continue;
							}
						}*/
					//	cout<<le<<"///"<<endl;
						for(int jo=0;jo<le/2;jo++){
							/*if(ss[i][j].size()<3){
								while(true){
									continue;
								}
							}*/
							int aa=ss[i][j].back();
							ss[i][j].pop_back();
							int bb=ss[i][j].back();
							ss[i][j].pop_back();
							int cc=ss[i][j].back();
							ss[i][j].pop_back();
							ans.pb(bb);
							ss[i][j].pb(bb);
						}
					//	cout<<11<<endl;
					}
					//cout<<endl;
					for(int j=0;j<(ss[i].size())-1;j++){
						for(int pp=0;pp<jj[j+1];pp++){
							/*if(ss[i][j].size()==0 or ss[i][j+1].size()==0){
								while(true){
									continue;
								}
							}*/
							int aa=ss[i][j].back();
							ss[i][j].pop_back();
							int bb=ss[i][j+1].front();
							ss[i][j+1].pop_front();

							int x=*ac.lower_bound(aa);
							ans.pb(x);
						}
					}
					break;
				}
			}
			if(ye){
				break;
			}


		}

		if(ye){
			cout<<-1<<'\n';
			continue;
		}
		cout<<ans.size()<<'\n';
		for(auto j:ans){
			cout<<j+1<<" ";
		}
		cout<<'\n';

		










	}


	return 0;
}

Compilation message

del13.cpp: In function 'int main()':
del13.cpp:84:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::deque<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for(int i=0;i<ss.size();i++){
      |               ~^~~~~~~~~~
del13.cpp:85:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |    for(int j=0;j<ss[i].size();j++){
      |                ~^~~~~~~~~~~~~
del13.cpp:88:10: warning: unused variable 'aa' [-Wunused-variable]
   88 |      int aa=ss[i][j].back();
      |          ^~
del13.cpp:92:10: warning: unused variable 'cc' [-Wunused-variable]
   92 |      int cc=ss[i][j].back();
      |          ^~
del13.cpp:103:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |    for(int j=0;j<ss[i].size();j++){
      |                ~^~~~~~~~~~~~~
del13.cpp:110:23: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |     if(ss[i][1].size()>=j and ss[i][0].size()>=j and ss[i][0].size()%2==j%2){
      |        ~~~~~~~~~~~~~~~^~~
del13.cpp:110:46: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |     if(ss[i][1].size()>=j and ss[i][0].size()>=j and ss[i][0].size()%2==j%2){
      |                               ~~~~~~~~~~~~~~~^~~
del13.cpp:110:71: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |     if(ss[i][1].size()>=j and ss[i][0].size()>=j and ss[i][0].size()%2==j%2){
      |                                                      ~~~~~~~~~~~~~~~~~^~~~~
del13.cpp:116:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |    for(int j=2;j<ss[i].size();j++){
      |                ~^~~~~~~~~~~~~
del13.cpp:117:43: error: no matching function for call to 'min(int, std::deque<int>::size_type)'
  117 |     for(int jj=0;jj<=min(2,ss[i][j].size());jj++){
      |                                           ^
In file included from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from del13.cpp:10:
/usr/include/c++/9/bits/stl_algobase.h:198:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  198 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:198:5: note:   template argument deduction/substitution failed:
del13.cpp:117:43: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::deque<int>::size_type' {aka 'long unsigned int'})
  117 |     for(int jj=0;jj<=min(2,ss[i][j].size());jj++){
      |                                           ^
In file included from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from del13.cpp:10:
/usr/include/c++/9/bits/stl_algobase.h:246:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  246 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:246:5: note:   template argument deduction/substitution failed:
del13.cpp:117:43: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::deque<int>::size_type' {aka 'long unsigned int'})
  117 |     for(int jj=0;jj<=min(2,ss[i][j].size());jj++){
      |                                           ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from del13.cpp:10:
/usr/include/c++/9/bits/stl_algo.h:3444:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3444 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3444:5: note:   template argument deduction/substitution failed:
del13.cpp:117:43: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  117 |     for(int jj=0;jj<=min(2,ss[i][j].size());jj++){
      |                                           ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from del13.cpp:10:
/usr/include/c++/9/bits/stl_algo.h:3450:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3450 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3450:5: note:   template argument deduction/substitution failed:
del13.cpp:117:43: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  117 |     for(int jj=0;jj<=min(2,ss[i][j].size());jj++){
      |                                           ^
del13.cpp:156:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |      for(int j=0;j<ss[i].size();j++){
      |                  ~^~~~~~~~~~~~~
del13.cpp:159:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |      for(int j=0;j<ss[i].size();j++){
      |                  ~^~~~~~~~~~~~~
del13.cpp:178:12: warning: unused variable 'aa' [-Wunused-variable]
  178 |        int aa=ss[i][j].back();
      |            ^~
del13.cpp:182:12: warning: unused variable 'cc' [-Wunused-variable]
  182 |        int cc=ss[i][j].back();
      |            ^~
del13.cpp:190:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |      for(int j=0;j<(ss[i].size())-1;j++){
      |                  ~^~~~~~~~~~~~~~~~~
del13.cpp:199:12: warning: unused variable 'bb' [-Wunused-variable]
  199 |        int bb=ss[i][j+1].front();
      |            ^~