### Pi-nan's blog

By Pi-nan, history, 18 months ago,

can anyone explain to me how to solve this problem Ceil and Duel using min-cost max flow?

my approach was to build a flow network i.e. if node i have atk value >= node j ceil value then there will be an edge from j to i with capacity 1 and cost (atk[i]-ceil[j]), similarly if node i has def value > node j ceil value then there will be edge from j to i with capacity 1 and cost 0, and then connect all ceil's node to super source i.e. superSource -> ceil, and connect all atk and def node to super sink i.e. atk/def -> superSink with capacity 1 and cost 0. after building this network we will find min_cost_max_flow and after this, if all atk/def nodes are visited then we will add ceil[i] such that ceil's ith node is not used. I don't know why this is failing on test 28.

• +1

By Pi-nan, history, 3 years ago,

I am getting below run time error in Codeforces, though code works as expected in my local compiler. Time: 0 ms, memory: 0 KB Verdict: RUNTIME_ERROR I submitted my code for http://codeforces.com/contest/962/problem/D

Code is below.

# include<bits/stdc++.h>

using namespace std;

int main() {

int n;
cin >> n;
vector<int>a(n);
map<int,set<int>>m;
for(int i=0;i<n;i++)
{
cin >> a[i];
m[a[i]].insert(i);
}
map<int,set<int>>::iterator it;
int flag=1;
while(flag)
{
flag=0;
for(it=m.begin();it!=m.end();it++)
if(it->second.size()>=2)
{
flag=1;
break;
}
if(flag==0)
break;
set<int>:: iterator it1;
set<int>s1;
s1=it->second;
it1 = s1.begin();
int val = it->first;
int gh = *it1;
s1.erase(it1);
it1++;
int kl = *it1;
s1.erase(it1);
if(s1.size()==0)
m.erase(val);
else
it->second=s1;
val*=2;
m[val].insert(kl);
}
vector<int>ans(n,-1);
int cnt=0;
for(it=m.begin();it!=m.end();it++)
{
set<int>::iterator it1;
set<int>s2;
s2=it->second;
it1=s2.begin();
int val = it->first;
for(it1=s2.begin();it1!=s2.end();it1++)
{
ans[*it1]=val;
cnt++;
}
}
cout << cnt << "\n";
for(int i=0;i<n;i++)
if(ans[i]!=-1)
cout << ans[i] << " ";
return 0;


}

Unable to understand the error. Please suggest how to solve it.