This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+6;
int A[MAXN],n,m;
vector<pair<int,int> >no_zero;
vector<pair<int,int> >no_one;
vector<pair<int,int> >one;
vector<pair<int,int> >zero;
vector<pair<pair<int,int>,int> >onezero;
int arr[MAXN];
bool done[2*MAXN];
struct condition
{
int l,r,k,val;
};
int main()
{
memset(arr,-1,sizeof(arr));
cin>>n>>m;
if(n<=18&&m<=200)
{
vector<condition>c;
for(int i=0;i<m;i++)
{
int l,r,k,v;
cin>>l>>r>>k>>v;
c.push_back({l,r,k,v});
}
for(int mask=0;mask<(1<<n);mask++)
{
for(int i=0;i<n;i++)
{
if(mask&(1<<i))A[i]=1;
else A[i]=0;
}
bool ok=true;
for(auto xd:c)
{
vector<int>v;
for(int j=xd.l;j<=xd.r;j++)
{
v.push_back(A[j]);
}
sort(v.begin(),v.end());
if(v[xd.k-1]!=xd.val)
{
ok=false;break;
}
}
if(ok)
{
for(int i=0;i<n;i++)
{
cout<<A[i]<<" ";
}
cout<<endl;
return 0;
}
}
cout<<"-1\n";
return 0;
}
for(int i=0;i<m;i++)
{
int l,r,k,val;
cin>>l>>r>>k>>val;
l++;r++;
if(k==1&&val==1)no_zero.push_back({l,r});
if(k==r-l+1&&val==1)one.push_back({l,r});
if(k==1&&val==0)zero.push_back({l,r});
if(k==r-l+1&&val==0)no_one.push_back({l,r});
}
for(auto xd:no_zero)
{
for(int i=xd.first;i<=xd.second;i++)
{
arr[i]=1;
}
}
for(auto xd:no_one)
{
for(int i=xd.first;i<=xd.second;i++)
{
if(arr[i]==1)
{
cout<<"-1\n";
return 0;
}
arr[i]=0;
}
}
//for(int i=1;i<=n;i++)cout<<arr[i]<<" ";
//cout<<endl;
for(auto xd:one)
{
bool found=0;
for(int i=xd.first;i<=xd.second;i++)
{
if(arr[i]==1)found=1;
}
if(!found)onezero.push_back({xd,1});
}
for(auto xd:zero)
{
bool found=0;
for(int i=xd.first;i<=xd.second;i++)
{
if(arr[i]==0)found=1;
}
if(!found)onezero.push_back({xd,0});
}
for(int i=1;i<=n;i++)
{
if(arr[i]>=0)continue;
int minr=n+1,what=-1;
for(int j=0;j<onezero.size();j++)
{
if(done[j]==0&&onezero[j].first.second<minr)
{
minr=onezero[j].first.second;
what=onezero[j].second;
}
}
if(what==-1)
{
arr[i]=0;
}
else arr[i]=what;
for(int j=0;j<onezero.size();j++)
{
if(onezero[j].first.first<=i&&onezero[j].first.second>=i&&onezero[j].second==arr[i])
{
done[j]=1;
}
}
}
//for(int i=1;i<=n;i++)cout<<arr[i]<<" ";
//cout<<endl;
for(int i=0;i<onezero.size();i++)
{
if(done[i]==0)
{
cout<<"-1\n";
return 0;
}
}
for(int i=1;i<=n;i++)cout<<arr[i]<<" ";
cout<<endl;
return 0;
}
Compilation message (stderr)
restore.cpp: In function 'int main()':
restore.cpp:116:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for(int j=0;j<onezero.size();j++)
| ~^~~~~~~~~~~~~~~
restore.cpp:129:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for(int j=0;j<onezero.size();j++)
| ~^~~~~~~~~~~~~~~
restore.cpp:139:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | for(int i=0;i<onezero.size();i++)
| ~^~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |