oj.uz

Submission #242146

# Submission time Handle Problem Language Result Execution time Memory
242146 2020-06-27T01:49:14 Z Nayeon_A_Bunny Telefoni (COCI17_telefoni) C++17
40 / 80
 1000 ms 5744 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename TH>
void _dbg(const char* sdbg, TH h) {
	cerr << sdbg << " = " << h << "\n";
}

template<typename TH, typename... TA>
void _dbg(const char* sdbg, TH h, TA... t) {
	while (*sdbg != ',') cerr << *sdbg++;
	cerr << " = " << h << ",";
	_dbg(sdbg + 1, t...);
}

#define db(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define chkpt cerr << "------\n";

const int N=3e5+5,INF=1e9;

int n,d,a[N];
int nxt[N],b[N];

void Sub1(){
    int ans=INF;
    vector<int> freePosList;
    for(int i=1;i<=n;++i){
        if(a[i]==0){
            freePosList.push_back(i);
        }
    }
    int nFree=freePosList.size();
    int maxBit=1<<nFree;
    for(int mask=0;mask<maxBit;++mask){
//        if(mask!=4){
//            continue;
//        }
        for(int i=1;i<=n;++i){
            if(a[i]==1){
                b[i]=1;
            }
        }
        for(int i=0;i<nFree;++i){
            b[freePosList[i]]=(mask>>i)&1;
        }
        nxt[n]=n+1;
        for(int i=n-1;i>=1;--i){
            nxt[i]=(b[i+1]==1)?(i+1):nxt[i+1];
        }
        int i=1;
        while(i<n){
            if(nxt[i]-i>d){
                break;
            }
            i=nxt[i];
        }
        if(i==n){
//            if(__builtin_popcount(mask)==1){
//                for(int i=0;i<nFree;++i){
//                    if((mask>>i)&1){
//                        db(freePosList[i]);
//                    }
//                }
//                db(mask);
//                chkpt;
//            }
            ans=min(ans,__builtin_popcount(mask));
        }
    }
    cout<<ans<<'\n';
}

int main() {
//    freopen("COCI17_TELEFONI.INP","r",stdin);
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>d;
	for(int i=1;i<=n;++i){
        cin>>a[i];
	}
	Sub1();
//	nxt[n]=n+1;
//	for(int i=n-1;i>=1;--i){
//        nxt[i]=a[i+1]?(i+1):nxt[i+1];
//	}
//	int last=1;
//	while(last<=n){
//        if(nxt[last]-last>d){
//            break;
//        }
//        last=nxt[last];
//	}
//	int ans=0;
//	if(last<n){
//        last+=d;
//        while(last<n){
//            ans+=a[last]==0;
//            last+=d;
//        }
//	}
//	cout<<ans<<'\n';
	return 0;
}

Subtask #1
40.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 10 ms 384 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Incorrect 379 ms 480 KB Output isn't correct
7 Incorrect 5 ms 384 KB Output isn't correct
8 Execution timed out 1086 ms 5744 KB Time limit exceeded
9 Incorrect 50 ms 5740 KB Output isn't correct
10 Incorrect 250 ms 5740 KB Output isn't correct