제출 #722700

#제출 시각아이디문제언어결과실행 시간메모리
722700groshiRestore Array (RMI19_restore)C++17
100 / 100
13 ms1312 KiB
#include<iostream> #include<queue> #include<vector> using namespace std; int s[6000]; int sumy[6000]; int t[11000][5]; bool ustawione[6000]; struct wi{ vector<int> Q; int odl=1e9; bool odw=0; }*w; int32_t main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); int n,m; cin>>n>>m; int maxx=0; for(int i=1;i<=m;i++) cin>>t[i][0]>>t[i][1]>>t[i][2]>>t[i][3]; for(int i=1;i<=m;i++) maxx=max(maxx,t[i][2]); bool brak=1; for(int i=1;i<=m;i++) if(t[i][2]!=1 && t[i][2]!=t[i][1]-t[i][0]+1) brak=0; if(n<=18 && m<=200) { for(int i=0;i<(1<<n);i++) { for(int j=0;j<n;j++) { int pom=i&(1<<j); if(pom>0) s[j]=1; else s[j]=0; } sumy[0]=s[0]; for(int j=1;j<n;j++) sumy[j]=sumy[j-1]+s[j]; bool git=0; for(int j=1;j<=m;j++) { int x=t[j][0]; int y=t[j][1]; int mam=sumy[y]; if(x>0) mam-=sumy[x-1]; if(t[j][3]==0) { if(mam<t[j][2]) { git=1; break; } } else{ if(mam>t[j][2]-1) { git=1; break; } } } if(git==0) { for(int j=0;j<n;j++) cout<<!s[j]<<" "; cout<<"\n"; return 0; } } cout<<"-1"; return 0; } else if(maxx==1){ for(int i=1;i<=m;i++) if(t[i][3]==1) for(int a=t[i][0];a<=t[i][1];a++) s[a]=1; for(int i=1;i<=m;i++) { if(t[i][3]==0) { int suma=0; for(int a=t[i][0];a<=t[i][1];a++) suma+=s[a]; if(suma==t[i][1]-t[i][0]+1) { cout<<"-1"; return 0; } } } for(int i=0;i<n;i++) cout<<s[i]<<" "; } else if(brak){ bool git=0; for(int i=1;i<=m;i++) { if(t[i][3]==1 && t[i][2]==1) for(int a=t[i][0];a<=t[i][1];a++) { if(ustawione[a]==1 && s[a]==0) { git=1; break; } s[a]=1,ustawione[a]=1; } if(t[i][3]==0 && t[i][2]!=1) for(int a=t[i][0];a<=t[i][1];a++) { if(s[a]==1) { git=1; break; } ustawione[a]=1; } if(git) { cout<<"-1"; return 0; } } for(int i=1;i<=m;i++) { bool git=0; if(t[i][3]==1 && t[i][2]==1) continue; if(t[i][3]==0 && t[i][2]!=1) continue; int chce=t[i][3]; int puste=0; int gdzie=0; for(int a=t[i][0];a<=t[i][1];a++) { if(ustawione[a]==1 && s[a]==chce) { git=1; break; } if(ustawione[a]==0) { puste++; gdzie=a; } } if(git) continue; if(puste==0) { cout<<"-1"; return 0; } if(puste==1) { ustawione[gdzie]=1; s[gdzie]=chce; } } int pop=0; for(int i=0;i<n;i++) { if(ustawione[i]) continue; s[i]=pop; pop++; pop%=2; } for(int i=0;i<n;i++) cout<<s[i]<<" "; return 0; } else{ int a,b,c,d; w=new wi[n+3]; w[0].Q.push_back(1); w[0].Q.push_back(0); for(int i=1;i<n;i++) { w[i].Q.push_back(i+1); w[i].Q.push_back(1); } for(int i=n;i>=1;i--) { w[i].Q.push_back(i-1); w[i].Q.push_back(0); } for(int i=1;i<=m;i++) { a=t[i][0]; b=t[i][1]; c=t[i][2]; d=t[i][3]; a++; b++; if(d==1) { w[b].Q.push_back(a-1); w[b].Q.push_back(-(b-a+1)+c-1); } else{ w[a-1].Q.push_back(b); w[a-1].Q.push_back(b-a+1-c); } } priority_queue<pair<int,int> > kolejka; kolejka.push({0,0}); w[0].odl=0; bool k=0; while(!kolejka.empty()) { auto para=kolejka.top(); kolejka.pop(); w[para.second].odw=1; for(int i=0;i<w[para.second].Q.size();i+=2) { if(w[para.second].odl+w[para.second].Q[i+1]<w[w[para.second].Q[i]].odl) { w[w[para.second].Q[i]].odl=w[para.second].odl+w[para.second].Q[i+1]; auto parap=make_pair(w[w[para.second].Q[i]].odl*(-1),w[para.second].Q[i]); kolejka.push(parap); } if(w[w[para.second].Q[i]].odw && w[w[para.second].Q[i]].odl<0) { k=1; break; } } if(k==1) break; } if(k==1) cout<<"-1"; else{ for(int i=1;i<=n;i++) { cout<<w[i].odl-w[i-1].odl<<" "; } } return 0; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

restore.cpp: In function 'int32_t main()':
restore.cpp:223:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  223 |         for(int i=0;i<w[para.second].Q.size();i+=2)
      |                     ~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...