Submission #500413

#TimeUsernameProblemLanguageResultExecution timeMemory
500413HediChehaidarJob Scheduling (CEOI12_jobs)C++17
100 / 100
161 ms13888 KiB
/* ID: hedichehaidar TASK: cowtour LANG: C++11 */ #include<bits/stdc++.h> typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef double db; ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD) ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM) #define ss second #define ff first #define all(x) (x).begin() , (x).end() #define pb push_back #define vi vector<int> #define vii vector<pair<int,int>> #define vl vector<ll> #define vll vector<pair<ll,ll>> #define pii pair<int,int> #define pll pair<ll,ll> #define pdd pair<double,double> #define vdd vector<pdd> #define dte tuple<double , double , double> using namespace std; const int INF = 1000*1000*1000; // 1 e 9 const int MOD = 998244353; const double EPS = 0.000000001; // 1 e -9 const ll inf = (ll)1e18; vi task[(int)1e5 + 10]; int need[(int)1e5 + 10]; int main(){ //ifstream fin ("testing.txt"); //ofstream fout ("output.txt"); ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); ll n , d , m; cin>>n>>d>>m; for(int i = 0 ; i < m ; i++){ int x; cin>>x; task[x].pb(i + 1); } int l = 1 , r = m , ans = m; while(l <= r){ int mid = (l+r) / 2; bool ok = true; int cur = 0 , all = 0; for(int i = 1 ; i <= n ; i++) need[i] = 0; for(int i = 1 ; i <= n ; i++){ need[i] += need[i - 1]; //if(mid == 1) cout << need[i] << " " << cur << " "; need[i + d] += task[i].size(); all += task[i].size(); cur += min(all , mid); all -= min(all , mid); if(cur < need[i]){ ok = false; break; } } //if(mid == 1) cout << "\n"; if(ok){ ans = mid; r = mid - 1; } else l = mid + 1; } queue<int> q; cout << ans << "\n"; for(int i = 1 ; i <= n ; i++){ for(auto c : task[i]) q.push(c); for(int j = 0 ; j < ans ; j++){ if(q.empty()) break; cout << q.front() << " "; q.pop(); } cout << 0 << "\n"; } return 0; } /* Think of : BS / DFS / BFS / SSSP / SCC / MSP / MAX FLOW / TOPSORT / LCA / MATRIX / DP(bitmask) / 2 POINTERS / SEG TREE / MATH / UN FIND / MO / HLD Read the statement CAREFULLY !! Make a GREADY APPROACH !!!! (start from highest / lowest) Make your own TESTS !! Be careful from CORNER CASES ! */
#Verdict Execution timeMemoryGrader output
Fetching results...