Problem-CLEANUP Problem - CodeChef
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--)
{
int n, m;
int i=1, j=1;
// map-true if job completed
cin >> n >> m;
vector<bool> jobs(n + 1, false);
vector<int> chef, assi;
for (int i = 0; i < m; i++)
{
int temp;
cin >> temp;
jobs[temp] = true;
}
for (int x = 1; i < n; x++)
{
if (jobs[x] == false)
{
i = j = x;
break;
}
}
while (i <= n)
{
j++;
while (j <= n && jobs[j] == true)
j++;
if (i <= n)
chef.push_back(i);
if (j <= n)
assi.push_back(j);
i = j + 1;
while (i <= n && jobs[i] == true)
i++;
j = i;
}
for (int f=0;f<chef.size();f++)
{
cout << chef[f] << " ";
}
cout<<endl;
for (int f=0;f<assi.size();f++)
{
cout << assi[f] << " ";
}
cout<<endl;
}
return 0;
}
Sorry, I had old code in the post. Now, i & j are initialized by 1. I tried all the the test cases and edge cases that I could think of & it still doesn’t work.
IDK how you do this. Thanks a lot.
1 Like
I see. How can I write one myself? I could test other people’s solution with mine and see what’s wrong. Thanks for the information.
ssjgz
August 18, 2021, 7:39pm
8
Here’s the solution (+ testcase generator) I wrote for this Problem:
//
// Solution to: https://www.codechef.com/problems/CLEANUP
//
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cassert>
#include <sys/time.h> // TODO - this is only for random testcase generation. Remove it when you don't need new random testcases!
using namespace std;
template <typename T>
T read()
{
T toRead;
cin >> toRead;
assert(cin);
return toRead;
}
std::pair<vector<int>, vector<int>> findChefAndAssistantJobs(const int numJobs, const vector<int>& completedJobs)
{
vector<int> chefJobs;
vector<int> assistantJobs;
set<int> allJobs;
for (int i = 1; i<= numJobs; i++)
{
allJobs.insert(i);
}
for (const auto completedJob : completedJobs)
{
allJobs.erase(completedJob);
}
vector<int> remainingJobs(allJobs.begin(), allJobs.end());
for (int i = 0; i < allJobs.size(); i += 2)
{
chefJobs.push_back(remainingJobs[i]);
}
for (int i = 1; i < allJobs.size(); i += 2)
{
assistantJobs.push_back(remainingJobs[i]);
}
return {chefJobs, assistantJobs};
}
int main(int argc, char* argv[])
{
ios::sync_with_stdio(false);
if (argc == 2 && string(argv[1]) == "--test")
{
struct timeval time;
gettimeofday(&time,NULL);
srand((time.tv_sec * 1000) + (time.tv_usec / 1000));
//const int T = rand() % 100 + 1;
const int T = 1;
cout << T << endl;
for (int t = 0; t < T; t++)
{
const int numJobs = rand() % 20;
const int numCompletedJobs = rand() % (numJobs + 1);
vector<int> allJobs;
for (int i = 1; i <= numJobs; i++)
{
allJobs.push_back(i);
}
random_shuffle(allJobs.begin(), allJobs.end());
vector<int> completedJobs(allJobs.begin(), allJobs.begin() + numCompletedJobs);
cout << numJobs << " " << numCompletedJobs << endl;
for (int i = 0; i < completedJobs.size(); i++)
{
cout << completedJobs[i];
if (i != completedJobs.size() - 1)
cout << " ";
}
cout << endl;
}
return 0;
}
const auto T = read<int>();
for (int t = 0; t < T; t++)
{
const int numJobs = read<int>();
const int numCompletedJobs = read<int>();
vector<int> completedJobs(numCompletedJobs);
for(auto& jobId : completedJobs)
jobId = read<int>();
const auto& [chefJobs, assistantJobs] = findChefAndAssistantJobs(numJobs, completedJobs);
auto printJobsDone = [](const vector<int>& jobsDone)
{
for (int i = 0; i < jobsDone.size(); i++)
{
cout << jobsDone[i];
if (i != jobsDone.size() - 1)
cout << " ";
}
cout << endl;
};
printJobsDone(chefJobs);
printJobsDone(assistantJobs);
}
assert(cin);
}
Compile, and
./a.out --test > testcase.txt; cat testcase.txt | ./a.out
to write a testcase to testcase.txt
and print out the answer.
3 Likes