In the third problem of Google’s CodeJam,Parenting Partening Returns,my code is missing some small edge case. I have tried many variations in test cases, they all worked but still I am getting wrong answer.
Here is my solution:
#include<bits/stdc++.h> using namespace std; int main() { int t; cin>>t; for(int test=1;test<=t;test++) { int n; cin>>n; vector<pair<pair<int,int>,int>> a; char ans[n]; int s,e; bool impossible=false; for(int i=0;i<n;i++) { cin>>s>>e; a.push_back(make_pair(make_pair(s,e),i)); } sort(a.begin(),a.end()); ans[a[0].second]='C'; for(int i=0;i<n-1;i++) { if(a[i].first.second<=a[i+1].first.first) { ans[a[i+1].second]=ans[a[i].second]; } else { int temp=a[i].first.second<a[i+1].first.second?a[i].first.second:a[i+1].first.second; if(i<n-2&&a[i+2].first.first<temp){ impossible=true; break; } if(ans[a[i].second]=='C') ans[a[i+1].second]='J'; else ans[a[i+1].second]='C'; } } cout<<"Case #"<<test<<": "; if(impossible) cout<<"IMPOSSIBLE\n"; else { for(int i=0;i<n;i++) cout<<ans[i]; cout<<"\n"; } } return 0; }