fork download
copy 
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4. #include<utility>
  5. #include <sstream>
  6. #include <stdlib.h>
  7. using namespace std;
  8. #define ll long long
  9.  
  10. std::string repeat(int n) {
  11.     std::ostringstream os;
  12.     for(int i = 0; i < n; i++)
  13.         os << "repeat";
  14.     return os.str();
  15. }
  16.  
  17. struct {
  18.   bool operator()(pair<ll,ll> item1, pair<ll,ll> item2) const {
  19.     if(item1.second > item2.second) {
  20.       return true;
  21.     }
  22.     else if(item1.second < item2.second) {
  23.       return false;
  24.     }
  25.     else {
  26.       if(item1.first >= item2.first) {
  27.         return false;
  28.       }
  29.       else {
  30.         return true;
  31.       }
  32.     }
  33.   }
  34. } customLess;
  35.  
  36. int main() {
  37.   std::ios::sync_with_stdio(false);
  38.   int t;
  39.   cin>>t;
  40.   for (int _=0; _<t; _++) {
  41.     ll n,m;
  42.     cin>>n>>m;
  43.     vector< pair<ll,ll> > intervals;
  44.     for (ll i=0; i<n; i++) {
  45.       ll lower,upper;
  46.       cin>>lower>>upper;
  47.       intervals.push_back(make_pair(lower,upper));
  48.     }
  49.     sort(intervals.begin(), intervals.end(), customLess);
  50.     string k;
  51.     cin>>k;
  52.  
  53.     vector< pair<ll,ll> > bestIntervals;
  54.     bestIntervals.push_back(intervals[0]);
  55.     ll lowerLevel = intervals[0].first;
  56.     ll remaining = m-1;
  57.  
  58.     ll i = 1;
  59.     while(i<n) {
  60.       pair<ll,ll> currentInterval = intervals[i];
  61.       if(remaining == 0) {
  62.         break;
  63.       }
  64.       if(currentInterval.first >= lowerLevel) {
  65.         i += 1;
  66.         continue;
  67.       }
  68.       else {
  69.         if(currentInterval.second < lowerLevel) {
  70.           bestIntervals.push_back(currentInterval);
  71.           lowerLevel = currentInterval.first;
  72.           remaining -= 1;
  73.           i += 1;
  74.         }
  75.         else {
  76.           pair<ll,ll> bestInterval;
  77.           ll bestRange = 0;
  78.           while(i < n && currentInterval.second >= lowerLevel-1) {
  79.             ll extraRangeCoverUp = lowerLevel - currentInterval.first;
  80.             if(bestRange < extraRangeCoverUp) {
  81.               bestRange = extraRangeCoverUp;
  82.               bestInterval = currentInterval;
  83.             }
  84.             i += 1;
  85.             if(i<n) {
  86.               currentInterval = intervals[i];
  87.             }
  88.           }
  89.           bestIntervals.push_back(make_pair(bestInterval.first,min(bestInterval.second,lowerLevel)));
  90.           lowerLevel = bestInterval.first;
  91.           remaining -= 1;
  92.         }
  93.       }
  94.     }
  95.  
  96.     reverse(bestIntervals.begin(),bestIntervals.end());
  97.     vector<ll> shift;
  98.     shift.push_back(bestIntervals[0].first);
  99.     for(vector< pair<ll,ll> >::iterator interval = bestIntervals.begin();
  100.         interval != bestIntervals.end();
  101.         ++interval) {
  102.           for(int i=(*interval).first; i<(*interval).second+1; i++) {
  103.             if(i == shift.back()) {
  104.               continue;
  105.             }
  106.             else {
  107.               shift.push_back(i);
  108.             }
  109.           }
  110.         }
  111.  
  112.     ll numberOfShifts = shift.size();
  113.     reverse(k.begin(),k.end());
  114.  
  115.     ll kLen = k.length();
  116.     ll sum[kLen+shift.back()];
  117.     for(ll i=0; i<shift.back()+kLen; i++) {
  118.       sum[i] = 0;
  119.     }
  120.     for(ll i=0; i<numberOfShifts; i++) {
  121.       for(ll j=0; j<kLen; j++) {
  122.         sum[shift[i]+j] += (ll)k[j]-48;
  123.       }
  124.     }
  125.  
  126.     ll carry = 0;
  127.     string ans = "";
  128.     for(ll i=0; i<kLen+shift.back(); i++) {
  129.       ans += to_string((carry+sum[i])%2);
  130.       carry = (carry+sum[i])/2;
  131.     }
  132.     while(carry != 0) {
  133.       ans += to_string(carry%2);
  134.       carry /= 2;
  135.     }
  136.  
  137.     reverse(ans.begin(),ans.end());
  138.     cout<<ans<<'\n';
  139.   }
  140.   return 0;
  141. }
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
1 


3 2 


0 1 


2 3 


4 4 


110
stdout
copy 
10101000
https://ideone.com/t7DDuD
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!