1659D - Reverse Sort Sum - CodeForces Solution


constructive algorithms data structures math two pointers

Please click on ads to support us..

Python Code:

import sys

def solve():
	inp = sys.stdin.readline
	n = int(input())
	c = list(map(int, inp().split()))
	a = ['0'] * n
	sub = [0] * (n + 1)
	have = 0
	j = 0
	cur = 0
	for i in range(0, n):
		sub[i - have + 1] += 1
		sub[i + 1] -= 1 
		if j >= i - have + 1:
			cur += 1
		while j < i - have:
			j += 1
			cur += sub[j]
		while j > i - have:
			cur -= sub[j]
			j -= 1
		if j >= 0 and cur < c[j]:
			a[i] = '1'
			sub[i] += i
			sub[i + 1] -= i
			if j == i:
				cur += i
			have += 1
			if i - have + 1 < i + 1:
				sub[i - have + 1] += 1
				sub[i - have + 2] -= 1
				if j == i - have + 1:
					cur += 1
	print(' '.join(a))


def main():
	for i in range(int(sys.stdin.readline())):
		solve()

if __name__ == '__main__':
	main()

C++ Code:

#pragma GCC optimize("Ofast")

#pragma GCC optimize("unroll-loops")

#pragma GCC optimize("inline")

#include<bits/stdc++.h>

using namespace std;

inline int my_getchar(){

  static char buf[1048576];

  static int s = 1048576;

  static int e = 1048576;

  if(s == e && e == 1048576){

    e = fread(buf, 1, 1048576, stdin);

    s = 0;

  }

  if(s == e){

    return EOF;

  }

  return buf[s++];

}

inline void rd(int &x){

  int k;

  int m=0;

  x=0;

  for(;;){

    k = my_getchar();

    if(k=='-'){

      m=1;

      break;

    }

    if('0'<=k&&k<='9'){

      x=k-'0';

      break;

    }

  }

  for(;;){

    k = my_getchar();

    if(k<'0'||k>'9'){

      break;

    }

    x=x*10+k-'0';

  }

  if(m){

    x=-x;

  }

}

inline void rd(long long &x){

  int k;

  int m=0;

  x=0;

  for(;;){

    k = my_getchar();

    if(k=='-'){

      m=1;

      break;

    }

    if('0'<=k&&k<='9'){

      x=k-'0';

      break;

    }

  }

  for(;;){

    k = my_getchar();

    if(k<'0'||k>'9'){

      break;

    }

    x=x*10+k-'0';

  }

  if(m){

    x=-x;

  }

}

inline int rd_int(void){

  int x;

  rd(x);

  return x;

}

struct MY_WRITER{

  char buf[1048576];

  int s;

  int e;

  MY_WRITER(){

    s = 0;

    e = 1048576;

  }

  ~MY_WRITER(){

    if(s){

      fwrite(buf, 1, s, stdout);

    }

  }

}

;

MY_WRITER MY_WRITER_VAR;

void my_putchar(int a){

  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){

    fwrite(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);

    MY_WRITER_VAR.s = 0;

  }

  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;

}

template<class T> inline void wt_L(vector<T> x);

template<class T> inline void wt_L(set<T> x);

template<class T> inline void wt_L(multiset<T> x);

template<class T1, class T2> inline void wt_L(pair<T1,T2> x);

inline void wt_L(char a){

  my_putchar(a);

}

inline void wt_L(long long x){

  int s=0;

  int m=0;

  char f[20];

  if(x<0){

    m=1;

    x=-x;

  }

  while(x){

    f[s++]=x%10;

    x/=10;

  }

  if(!s){

    f[s++]=0;

  }

  if(m){

    my_putchar('-');

  }

  while(s--){

    my_putchar(f[s]+'0');

  }

}

long long n;

long long a[200000+10];

long long b[200000+10];

long long c[200000+10];

long long ans[200000+10];

int main(){

  int PiIOrLma;

  int AuJVIghY = rd_int();

  for(PiIOrLma=(0);PiIOrLma<(AuJVIghY);PiIOrLma++){

    int i;

    rd(n);

    {

      int djQeACzd;

      for(djQeACzd=(0);djQeACzd<(n);djQeACzd++){

        rd(a[djQeACzd]);

      }

    }

    for(i=(0);i<(n);i++){

      c[i] = 0;

      b[i] = 0;

    }

    int EZ0PmQmu;

    long long zxsUT70f;

    if(n==0){

      zxsUT70f = 0;

    }

    else{

      zxsUT70f = a[0];

      for(EZ0PmQmu=(1);EZ0PmQmu<(n);EZ0PmQmu++){

        zxsUT70f += a[EZ0PmQmu];

      }

    }

    long long tt = zxsUT70f;

    tt /= n;

    long long sm = 0;

    for(i=(n)-1;i>=(0);i--){

      long long tg = i + 1;

      a[i] -= sm;

      if(a[i] >= tg && tt > 0){

        c[i] = 1;

        --tt;

        ++sm;

        b[i - tt]++;

      }

      sm -= b[i];

    }

    {

      int o8AZ1iEn;

      if(n==0){

        wt_L('\n');

      }

      else{

        for(o8AZ1iEn=(0);o8AZ1iEn<(n-1);o8AZ1iEn++){

          wt_L(c[o8AZ1iEn]);

          wt_L(' ');

        }

        wt_L(c[o8AZ1iEn]);

        wt_L('\n');

      }

    }

  }

  return 0;

}

template<class T> inline void wt_L(vector<T> x){

  int fg = 0;

  for(auto a : x){

    if(fg){

      my_putchar(' ');

    }

    fg = 1;

    wt_L(a);

  }

}

template<class T> inline void wt_L(set<T> x){

  int fg = 0;

  for(auto a : x){

    if(fg){

      my_putchar(' ');

    }

    fg = 1;

    wt_L(a);

  }

}

template<class T> inline void wt_L(multiset<T> x){

  int fg = 0;

  for(auto a : x){

    if(fg){

      my_putchar(' ');

    }

    fg = 1;

    wt_L(a);

  }

}

template<class T1, class T2> inline void wt_L(pair<T1,T2> x){

  wt_L(x.first);

  my_putchar(' ');

  wt_L(x.second);

}

// cLay version 20211231-1



// --- original code ---

// //no-unlocked

// ll n, a[2d5+10], b[2d5+10];

// ll c[2d5+10];

// ll ans[2d5+10];

// { 

//     REP(rd_int()){

//         rd(n, a(n));

//         rep(i, n) c[i] = 0, b[i] = 0;

//         ll tt = sum(a(n));

//         tt /= n;

//         ll sm = 0;

//         rrep(i, n){

//             ll tg = i + 1;

//             a[i] -= sm;

//             if(a[i] >= tg && tt > 0){

//                 c[i] = 1;

//                 --tt;

//                 ++sm;

//                 b[i - tt]++;

//             }

//             sm -= b[i];

//         }

//         wt(c(n));

//     }

// }

// 


Comments

Submit
0 Comments
More Questions

1475E - Advertising Agency
1345B - Card Constructions
1077B - Disturbed People
653A - Bear and Three Balls
794A - Bank Robbery
157A - Game Outcome
3B - Lorry
1392A - Omkar and Password
489A - SwapSort
932A - Palindromic Supersequence
433A - Kitahara Haruki's Gift
672A - Summer Camp
1277A - Happy Birthday Polycarp
577A - Multiplication Table
817C - Really Big Numbers
1355A - Sequence with Digits
977B - Two-gram
993A - Two Squares
1659D - Reverse Sort Sum
1659A - Red Versus Blue
1659B - Bit Flipping
1480B - The Great Hero
1519B - The Cake Is a Lie
1659C - Line Empire
515A - Drazil and Date
1084B - Kvass and the Fair Nut
1101A - Minimum Integer
985D - Sand Fortress
1279A - New Year Garland
1279B - Verse For Santa