Submission #317945

#TimeUsernameProblemLanguageResultExecution timeMemory
317945daniel920712DEL13 (info1cup18_del13)C++14
100 / 100
41 ms4192 KiB
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <vector> #include <queue> #include <map> #include <stack> #include <set> using namespace std; int all[100005]; int Father[1000005]; int Father2[1000005]; int xx[1000005]={0}; bool have[1000005]={0}; bool can[1000005]={0}; bool use[5][1000005]={0}; int DP[5][1000005]={0}; pair < int , int > Next[5][1000005]; vector < int > tt; vector < int > ttt; vector < int > ans; set < int > temp; int T,N,M; stack < int > aaa; bool F(int can,int here) { if(here==M+1) return 1-can; if(can==1&&ttt[here]<2) return 0; if(ttt[here]==0) { Next[can][here]=make_pair(0,here+1); return F(0,here+1); } if(use[can][here]) return DP[can][here]; DP[can][here]=0; if(can==1) { if(ttt[here]>=4) { if(F(1,here+1)) { Next[can][here]=make_pair(1,here+1); DP[can][here]=1; } } if(F(0,here+1)) { Next[can][here]=make_pair(0,here+1); DP[can][here]=1; } } else { if(F(1,here+1)) { Next[can][here]=make_pair(1,here+1); DP[can][here]=1; } } if(::can[here]) { if(F(0,here+1)) { Next[can][here]=make_pair(0,here+1); DP[can][here]=1; } } use[can][here]=1; return DP[can][here]; } void FF(int can,int here) { //printf("%d %d\n",can,here); if(here==M+1) return; FF(Next[can][here].first,Next[can][here].second); if(Next[can][here].first) xx[here+1]+=2; } void Find(int here) { int i; //printf("%d\n",here); if(have[here]) return; have[here]=1; vector < int > tt; for(i=0;i<N;i++) { if(here&(1<<i)) tt.push_back(i); } for(i=1;i<tt.size()-1;i++) { Father[here-(1<<tt[i-1])-(1<<tt[i+1])]=here; Father2[here-(1<<tt[i-1])-(1<<tt[i+1])]=tt[i]; Find(here-(1<<tt[i-1])-(1<<tt[i+1])); } } int main() { int i,j,con,ok=0,last,tt=0,ff=0,where; scanf("%d",&T); while(T--) { scanf("%d %d",&N,&M); ok=1; all[0]=0; for(i=1;i<=M;i++) scanf("%d",&all[i]); all[M+1]=N+1; ttt.clear(); for(i=0;i<=M;i++) { xx[i]=0; can[i]=0; ttt.push_back(all[i+1]-all[i]-1); } for(i=0;i<=M;i++) { use[0][i]=0; use[1][i]=0; if(ttt[i]%2) { if(i!=M&&ttt[i+1]>=1) { can[i]=1; can[i+1]=1; ttt[i]--; ttt[i+1]--; xx[i+1]++; } } if(ttt[i]%2) break; } if(i!=M+1) { printf("-1\n"); continue; } if(F(0,0)==0) printf("-1\n"); else { FF(0,0); ans.clear(); for(i=0;i<=M;i++) { temp.clear(); for(j=all[i]+1;j<all[i+1];j++) temp.insert(j); N=temp.size(); N-=xx[i]; N-=xx[i+1]; //printf("%d %d %d\n",all[i],all[i+1],N); for(j=0;j<N/2;j++) { tt=*next(temp.begin()); ans.push_back(tt); temp.erase(temp.upper_bound(tt)); temp.erase(prev(temp.lower_bound(tt))); } } for(i=0;i<=M;i++) while(xx[i]--) ans.push_back(all[i]); printf("%d\n",ans.size()); for(auto i:ans) printf("%d ",i); printf("\n"); } ok=1; } return 0; }

Compilation message (stderr)

del13.cpp: In function 'void Find(int)':
del13.cpp:91:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(i=1;i<tt.size()-1;i++)
      |             ~^~~~~~~~~~~~
del13.cpp: In function 'int main()':
del13.cpp:165:22: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  165 |             printf("%d\n",ans.size());
      |                     ~^    ~~~~~~~~~~
      |                      |            |
      |                      int          std::vector<int>::size_type {aka long unsigned int}
      |                     %ld
del13.cpp:101:13: warning: unused variable 'con' [-Wunused-variable]
  101 |     int i,j,con,ok=0,last,tt=0,ff=0,where;
      |             ^~~
del13.cpp:101:17: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  101 |     int i,j,con,ok=0,last,tt=0,ff=0,where;
      |                 ^~
del13.cpp:101:22: warning: unused variable 'last' [-Wunused-variable]
  101 |     int i,j,con,ok=0,last,tt=0,ff=0,where;
      |                      ^~~~
del13.cpp:101:32: warning: unused variable 'ff' [-Wunused-variable]
  101 |     int i,j,con,ok=0,last,tt=0,ff=0,where;
      |                                ^~
del13.cpp:101:37: warning: unused variable 'where' [-Wunused-variable]
  101 |     int i,j,con,ok=0,last,tt=0,ff=0,where;
      |                                     ^~~~~
del13.cpp:102:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  102 |     scanf("%d",&T);
      |     ~~~~~^~~~~~~~~
del13.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |         scanf("%d %d",&N,&M);
      |         ~~~~~^~~~~~~~~~~~~~~
del13.cpp:109:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  109 |         for(i=1;i<=M;i++) scanf("%d",&all[i]);
      |                           ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...