Blog entries - Codeforces

#	User	Rating
1	tourist	3880
2	jiangly	3669
3	ecnerwala	3654
4	Benq	3627
5	orzdevinwang	3612
6	Geothermal	3569
6	cnnfls_csy	3569
8	jqdai0815	3532
9	Radewoosh	3522
10	gyh20	3447

#	User	Contrib.
1	awoo	161
1	maomao90	161
3	adamant	156
4	maroonrk	153
5	-is-this-fft-	148
5	atcoder_official	148
5	SecondThread	148
8	Petr	147
9	nor	144
10	TheScrasse	142

shiny_shine's blog

My approach during CodeForces Round 959

By shiny_shine, history, 8 days ago, In English

0. Feeling

Welcome to the easiest Div.1 + Div.2 ever.

Got accepted on ABCDE.

And there's also a version in Chinese here.

1. Diverse Game

Given a permutation with a size of $$$nm$$$, construct another permutation with a size of $$$nm$$$ satisfies that it's different to the previous permutation in each position.

$$$a_i=a_i\bmod nm+1$$$. The time complexity is $$$O(nm)$$$.

Code

#include <iostream>
using namespace std;
const int N = 5e4 + 10;
int n, m;
void run()
{
    scanf("%d%d", &n, &m);
    if (n == 1 and m == 1)
    {
        scanf("%*d");
        puts("-1");
        return;
    }
    for (int i = 1, x; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &x);
            printf("%d%c", x % (n * m) + 1, " \n"[j == m]);
        }
    }
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

2. Fun Game

Given two binary sequences $$$a$$$ and $$$b$$$，unlimited operation to make from $$$a_l$$$ to $$$a_r$$$ simultaneously xor $$$a_1$$$ to $$$a_{r-l+1}$$$. Determine if it's able to turn $$$a$$$ into $$$b$$$.

Because I was watching Zenless Zone Zero videos on Bilibili, I suddenly realized that, it's able to consider the prefix zeros in $$$a$$$ and $$$b$$$ as "hollow". Because, under the constriants of the problem, regardless how many operations you do, the size of their "hollow" won't decrease.

With only one $$$1$$$, we can freely modify the following zeros and ones.

Only one line of code to solve this problem. The time complexity is $$$O(n)$$$.

Code

#include <iostream>
#include <string>
using namespace std;
const int N = 1e5 + 10;
int n;
string s, t;
void run()
{
    cin >> n >> s >> t;
    puts(s.find('1') <= t.find('1') ? "YES" : "NO");
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

3. Hungry Games

Too lazy to write the statement again.

Answer = total number of possible ranges — ranges with final toxicity of $$$0$$$.

Looks like topological sort.

Define $$$d_i$$$ as the number of left borders $$$j$$$ when set $$$i$$$ as the right border satisfying the final toxicity of the range $$$[j,i]$$$ equals zero.

When enumerating $$$i$$$, find the first $$$t$$$ safisfies $$$\sum_{j=i}^t a_j>x$$$, add $$$d_i+1$$$ to $$$d_t$$$. because, $$$d_i$$$ ranges satisfying the final toxicity equals zero, and the range $$$[i,t]$$$ also makes zero, it's able to combine these two ranges together, that the final toxicity is still zero.

The time complexity is $$$O(n)$$$.

Code

#include <iostream>
#include <cstring>
using namespace std;
const int N = 2e5 + 10;
using ll = long long;
int n, k, r;
ll a[N], dp[N], cur, res;
void run()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", a + i);
    }
    memset(dp + 2, 0, n << 3);
    cur = 0;
    r = 1;
    for (int i = 1; i <= n; i++)
    {
        cur -= a[i - 1];
        while (r <= n and cur <= k)
            cur += a[r], r++;
        if (cur <= k)
            continue;
        dp[r] += dp[i] + 1;
    }
    res = n;
    res *= n + 1;
    res /= 2;
    for (int i = 2; i <= n + 1; i++)
    {
        res -= dp[i];
    }
    printf("%lld\n", res);
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

4. Funny Game

In a complete graph with $$$n$$$ nodes, each node has a value $$$a_i$$$. The weight of the edge connecting node $$$i$$$ and $$$j$$$ is $$$|a_i-a_j|$$$. Find a spanning tree in this graph satisfying $$$i$$$ divides the weight of the $$$i$$$-th edge.

I didn't realize the pigeonhole here, so I had a different approach.

A smaller $$$i$$$ has an expectational bigger number of edges satisfying $$$i$$$ divides its weight.

So, enumerate $$$i$$$ in decreasing order, then use union-find to handle connected components.

The time complexity is $$$O(n^2)$$$.

Code

#include <iostream>
#include <list>
#include <cstring>
using namespace std;
const int N = 2e3 + 10;
int n, a[N], f[N], v[N], p;
bool fl;
using pii = pair<int, int>;
list<pii> ret;
inline int find(int x)
{
    return x == f[x] ? x : f[x] = find(f[x]);
}
inline void merge(int x, int y)
{
    f[find(y)] = find(x);
}
void run()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        f[i] = i;
        scanf("%d", a + i);
    }
    ret.clear();
    for (int i = n - 1; i; i--)
    {
        memset(v, 0, i << 2);
        fl = false;
        for (int j = 1; j <= n; j++)
        {
            p = a[j] % i;
            if (!v[p])
            {
                v[p] = j;
                continue;
            }
            if (find(j) == find(v[p]))
                continue;
            merge(j, v[p]);
            ret.push_front({j, v[p]});
            fl = true;
            break;
        }
        if (!fl)
            return puts("NO"), void();
    }
    puts("YES");
    for (auto &[tx, ty] : ret)
        printf("%d %d\n", tx, ty);
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

5. Wooden Game

Too lazy to rewrite the statement again.

The contribution of a tree with a size of $$$x$$$ is able to be any integer in range $$$[1,x]$$$, regardless its structure, because we can remove its leaves one by one.

When I realized that, I f**ked up.

The time complexity is $$$O(n\log n)$$$.

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int n, a[N], t, res;
void run()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", a + i);
        for (int j = 1; j < a[i]; j++)
            scanf("%*d");
    }
    sort(a + 1, a + n + 1);
    t = 1;
    for (; t < a[n]; t = t * 2 + 1)
        ;
    res = 0;
    for (int i = n; i; i--)
    {
        while ((t > a[i]) or (t & res))
            t--;
        res |= t;
    }
    printf("%d\n", res);
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

Full text and comments »

shiny_shine
8 days ago
2

Alternative __int128 without 64-bit compiler (Alpha version)

By shiny_shine, history, 4 months ago, In English

As you know, in this reason, 64-bit C++ compilers are temporarily disabled.

In order to keep using __int128 (at least partially) in 32-bit compilers, I'm trying writing a template of the unsigned version of __int128.

On 2024/3/15, I completed writing the alpha version of it.

If you find bugs in my code, please leave a comment below. Thanks!

UPD:

2024/3/14: added (maybe) all operators that an __int128 has except for operator/ / fixed infinite-recursion bug in several operators

2024/3/15: added operator/ / fixed many bugs in almost all arithmetic operators / completed first (buggy) version of this handmade __int128

Here's it:

integer_128_impl.cpp

#include<tuple>
#include<iostream>
#include<climits>

namespace RedshiftShine{
    
    using ll=unsigned long long;
    const ll ulmx=ULLONG_MAX;
    const ll shift=64;

    ll min(ll x,ll y){
        return x<y?x:y;
    }

    ll max(ll x,ll y){
        return x>y?x:y;
    }

    bool detect_overflow_add(ll x,ll y){
        return x+y<min(x,y);
    }

    bool detect_overflow_minus(ll x,ll y){
        return x<y;
    }

    class Custom_Unsigned_int128{
        private:
        ll higherInt,lowerInt;
        public:
        Custom_Unsigned_int128(){}

        template<typename _Tp>
        Custom_Unsigned_int128(_Tp x):
        higherInt(0),
        lowerInt(x){}

        template<typename _Tp>
        Custom_Unsigned_int128(_Tp x,_Tp y):
        higherInt(x),
        lowerInt(y){}
        
        Custom_Unsigned_int128
        (const Custom_Unsigned_int128& ele):
        higherInt(ele.higherInt),
        lowerInt(ele.lowerInt){}

        std::pair<ll,ll>
        base_access(){
            return std::pair<ll,ll>{
                higherInt,
                lowerInt
            };
        }

        Custom_Unsigned_int128&
        operator=(const Custom_Unsigned_int128& x){
            higherInt=x.higherInt,
            lowerInt=x.lowerInt;
            return *this;
        }

        template<typename _Tp>
        Custom_Unsigned_int128&
        operator=(const _Tp& x){
            *this=Custom_Unsigned_int128
            (
                0,x
            );
            return *this;
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        operator+(const _Tp& x){
            return Custom_Unsigned_int128
            (
                higherInt+
                detect_overflow_add(lowerInt,x),
                lowerInt+x
            );
        }

        template<typename _Tp>
        friend Custom_Unsigned_int128
        operator+(const _Tp& x,const Custom_Unsigned_int128& ele){
            return Custom_Unsigned_int128
            (
                ele.higherInt+
                detect_overflow_add(ele.lowerInt,x),
                ele.lowerInt+x
            );
        }

        Custom_Unsigned_int128
        operator+(const Custom_Unsigned_int128& x){
            return Custom_Unsigned_int128
            (
                higherInt+x.higherInt+
                detect_overflow_add(lowerInt,x.lowerInt),
                lowerInt+x.lowerInt
            );
        }

        template<typename _Tp>
        bool
        operator==(const _Tp& x)const{
            return 
            (
                !higherInt and 
                lowerInt==x
            );
        }

        template<typename _Tp>
        friend bool
        operator==(const _Tp& x,const Custom_Unsigned_int128& ele){
            return ele==x;
        }

        bool
        operator==(const Custom_Unsigned_int128& x)const{
            return 
            (
                higherInt==x.higherInt and 
                lowerInt==x.lowerInt
            );
        }

        template<typename _Tp>
        bool
        operator!=(const _Tp& x)const{
            return !(*this==x);
        }

        template<typename _Tp>
        friend bool
        operator!=(const _Tp& x,const Custom_Unsigned_int128& ele){
            return !(ele==x);
        }

        template<typename _Tp>
        bool
        operator<(const _Tp& x)const{
            return 
            (
                !higherInt and 
                lowerInt<x
            );
        }

        template<typename _Tp>
        friend bool
        operator<(const _Tp& x,const Custom_Unsigned_int128& ele){
            return 
            (
                ele.higherInt or 
                ele.lowerInt>x
            );
        }

        bool
        operator<(const Custom_Unsigned_int128& x)const{
            
            return 
            (
                higherInt<x.higherInt or 
                (
                    higherInt==x.higherInt and 
                    lowerInt<x.lowerInt
                )
            );
        }

        template<typename _Tp>
        bool
        operator<=(const _Tp& x)const{
            return 
            (
                *this<x or 
                *this==x
            );
        }

        template<typename _Tp>
        friend bool
        operator<=(const _Tp& x,const Custom_Unsigned_int128& ele){
            return ele<=x;
        }

        bool
        operator<=(const Custom_Unsigned_int128& x)const{
            return 
            (
                *this<x or 
                *this==x
            );
        }

        template<typename _Tp>
        bool
        operator>(const _Tp& x)const{
            return 
            !(
                *this<=x
            );
        }

        template<typename _Tp>
        friend bool
        operator>(const _Tp& x,const Custom_Unsigned_int128& ele){
            return !(ele<=x);
        }

        bool
        operator>(const Custom_Unsigned_int128& x)const{
            return 
            !(
                *this<=x
            );
        }

        template<typename _Tp>
        bool
        operator>=(const _Tp& x)const{
            return 
            !(
                *this<x
            );
        }

        template<typename _Tp>
        friend bool
        operator>=(const _Tp& x,const Custom_Unsigned_int128& ele){
            return !(ele<x);
        }

        bool
        operator>=(const Custom_Unsigned_int128& x)const{
            return 
            !(
                *this<x
            );
        }

        template<typename _Tp>
        Custom_Unsigned_int128&
        operator+=(const _Tp& x){
            return *this=*this+x;
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        operator-(const _Tp& x)const{
            return Custom_Unsigned_int128
            (
                higherInt-
                detect_overflow_minus(lowerInt,x),
                lowerInt-x
            );
        }

        Custom_Unsigned_int128
        operator-(const Custom_Unsigned_int128& x)const{
            return Custom_Unsigned_int128
            (
                higherInt-x.higherInt-
                detect_overflow_minus(lowerInt,x.lowerInt),
                lowerInt-x.lowerInt
            );
        }

        template<typename _Tp>
        Custom_Unsigned_int128&
        operator-=(const _Tp& x){
            return *this=*this-x;
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        operator&(const _Tp& x){
            return Custom_Unsigned_int128
            (
                0ull,
                lowerInt&x
            );
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        friend operator&(const _Tp& x,const Custom_Unsigned_int128& ele){
            return Custom_Unsigned_int128
            (
                ele.higherInt,
                ele.lowerInt&x
            );
        }

        Custom_Unsigned_int128
        operator&(const Custom_Unsigned_int128& x){
            return Custom_Unsigned_int128
            (
                higherInt&x.higherInt,
                lowerInt&x.lowerInt
            );
        }

        template<typename _Tp>
        Custom_Unsigned_int128&
        operator&=(const _Tp& x){
            return *this=*this&x;
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        operator|(const _Tp& x){
            return Custom_Unsigned_int128
            (
                higherInt,
                lowerInt|x
            );
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        friend operator|(const _Tp& x,const Custom_Unsigned_int128& ele){
            return Custom_Unsigned_int128
            (
                ele.higherInt,
                ele.lowerInt|x
            );
        }

        Custom_Unsigned_int128
        operator|(const Custom_Unsigned_int128& x){
            return Custom_Unsigned_int128
            (
                higherInt|x.higherInt,
                lowerInt|x.lowerInt
            );
        }

        template<typename _Tp>
        Custom_Unsigned_int128&
        operator|=(const _Tp& x){
            return *this=*this|x;
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        operator^(const _Tp& x){
            return Custom_Unsigned_int128
            (
                higherInt,
                lowerInt^x
            );
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        friend operator^(const _Tp& x,const Custom_Unsigned_int128& ele){
            return Custom_Unsigned_int128
            (
                ele.higherInt,
                ele.lowerInt^x
            );
        }

        Custom_Unsigned_int128
        operator^(const Custom_Unsigned_int128& x){
            return Custom_Unsigned_int128
            (
                higherInt^x.higherInt,
                lowerInt^x.lowerInt
            );
        }

        template<typename _Tp>
        Custom_Unsigned_int128&
        operator^=(const _Tp& x){
            return *this=*this^x;
        }

        Custom_Unsigned_int128
        operator~(){
            return Custom_Unsigned_int128(
                ~higherInt,
                ~lowerInt
            );
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        operator<<(const _Tp& x){
            return x<shift?
            Custom_Unsigned_int128(
                higherInt<<x|(lowerInt>>(shift-x)),
                lowerInt<<x
            ):
            Custom_Unsigned_int128(
                lowerInt<<(x-shift),
                0ull
            );
        }

        template<typename _Tp>
        Custom_Unsigned_int128&
        operator<<=(const _Tp& x){
            return *this=*this<<x;
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        operator>>(const _Tp& x){
            return x<shift?
            Custom_Unsigned_int128(
                higherInt>>x,
                lowerInt>>x|(higherInt<<(shift-x))
            ):
            Custom_Unsigned_int128(
                0ull,
                higherInt>>(x-shift)
            );
        }

        template<typename _Tp>
        Custom_Unsigned_int128&
        operator>>=(const _Tp& x){
            return *this=*this>>x;
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        operator*(const _Tp& x)const{
            Custom_Unsigned_int128 ret(0),pr(*this);
            _Tp tm(x);
            for(;tm;tm>>=1){
                if(tm&1)ret+=pr;
                pr<<=1;
            }
            return ret;
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        friend operator*(const _Tp& x,const Custom_Unsigned_int128& ele){
            Custom_Unsigned_int128 ret(0),pr(ele);
            _Tp tm(x);
            for(;tm!=0;tm>>=1){
                if((tm&1)!=0)ret+=pr;
                pr+=pr;
            }
            return ret;
        }

        template<typename _Tp>
        Custom_Unsigned_int128&
        operator*=(const _Tp& x){
            return *this=*this*x;
        }

        template<typename _Tp>
        Custom_Unsigned_int128
        operator/(const _Tp& x)const{
            Custom_Unsigned_int128 ret(0),pr(x),trm(1),ts(*this);
            while((!(pr.higherInt>>(shift-1))) and pr<=ts){
                
                pr<<=1,trm<<=1;
                
            }
            pr>>=1,trm>>=1;
            for(;;pr>>=1,trm>>=1){
                
                // if(ts<pr)continue;
                
                while(ts>=pr){
                    ts-=pr,ret+=trm;
                    
                }
                if((pr&1)!=0)break;
            }
            return ret;
        }

        template<typename _Tp>
        Custom_Unsigned_int128&
        operator/=(const _Tp& x){
            return *this=*this/x;
        }

        template<typename _Tp>
        _Tp
        operator%(const _Tp& x)const{
            return (*this-*this/x*x).lowerInt;
        }

        Custom_Unsigned_int128
        operator%(const Custom_Unsigned_int128& x)const{
            return *this-*this/x*x;
        }

        template<typename _Tp>
        Custom_Unsigned_int128&
        operator%=(const _Tp& x){
            return *this=*this%x;
        }

    };

}

void print(RedshiftShine::Custom_Unsigned_int128 v){
    if(v==0)return;
    print(v/10);
    putchar(v%10+'0');
}

void test(){
    RedshiftShine::Custom_Unsigned_int128 ci(0,1),cz(0,1);
    print(ci),putchar(' ');
    for(int i=128;i;i--){
        std::swap(ci,cz);
        cz+=ci;
        print(cz),putchar(' ');
    }
}

int main(){
    test();
}

Full text and comments »

shiny_shine
4 months ago
9

My imagination of translated problem statements in Luogu International

By shiny_shine, history, 5 months ago, In English

Abstract

After I post some wrong advice and got a number of downvotes, I came up with this idea to recollect some upvotes. When I heard that Luogu will release their international version with problem statements translated with LLM, I imagined how would these models translate them.

Full text and comments »

shiny_shine
5 months ago
1

Yet another advice for struggling greens/greys

By shiny_shine, history, 5 months ago, In English

Abstract

Suspend participating in Codeforces Rounds for a long time (at least a few months). During this time, try to participate in contests on other websites (AtCoder/Luogu/CodeChef or other). After that, when you participate in Codeforces Rounds again, your rating will surprisingly increase (at least for me). Here's why.

Full text and comments »

-9

shiny_shine
5 months ago
8

AtCoder taught me a lesson

By shiny_shine, history, 6 months ago, In English

Abstract

Never use reference value on std::priority_queue, otherwise it will be affected when you push in something "greater" than it.

Full text and comments »

shiny_shine
6 months ago
7

ConstructorU taught me a lesson

By shiny_shine, history, 6 months ago, In English

Abstract

Never apply a binary search on std::list.
If you want to make a custom _Comp function for std::set , write down as many instructions to distinguish elements in the set as possible.

Full text and comments »

shiny_shine
6 months ago
2

Don't be unrated anymore pls

By shiny_shine, history, 14 months ago, In English

There are 3 unrated contests in AtCoder after I registered my account

Full text and comments »

shiny_shine
14 months ago
5