# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1266652 | herominhsteve | Fire (BOI24_fire) | C++20 | 0 ms | 328 KiB |
#include <bits/stdc++.h>
#define el '\n'
#define FNAME "fire"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9+7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}
void setup(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
if (fopen(FNAME".inp","r")){
freopen(FNAME".inp","r",stdin);
freopen(FNAME".out","w",stdout);
}
}
struct Shift{
int s,e;
Shift(): s(0),e(0) {}
Shift(int S,int E): s(S), e(E){}
bool operator < (const Shift &other) const{
return (s<other.s or (s==other.s and e<other.e));
}
bool isOvernight(){
return (s>e);
}
};
int n,m;
vector<Shift> a;
void init(){
cin>>n>>m;
a.resize(n);
for (Shift &x: a) cin>>x.s>>x.e;
}
namespace Bitmask{
void solve(){
int MAXMASK = 1<<n;
int res = n;
for (int mask=1;mask<MAXMASK;mask++){
vector<Shift> t;
for (int i=0;i<n;i++){
if (mask & (1<<i)){
t.emplace_back(a[i]);
}
}
sort(allof(t));
t.emplace_back(t.front());
int num = __builtin_popcount(mask);
bool check=1;
int maxE=0;
int minS=m+1;
int overnight=0;
for (int i=1;i<=num;i++){
if (t[i-1].e < t[i].s){
check=0;
break;
}
maximize(maxE,t[i].e);
minimize(minS,t[i].s);
if (t[i].isOvernight()) overnight=1;
}
if (!overnight){
if (maxE != m) check=0;
else if (minS!=0) check=0;
}
if (check) minimize(res,num);
}
cout<< (res==n ? -1 : res);
exit(0);
}
};
void sol(){
if (n<=20) Bitmask::solve();
}
int main(){
setup();
init();
sol();
}
Compilation message (stderr)
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |