Submission #862621

#	Time	Username	Problem	Language	Result	Execution time	Memory
862621		Hanksburger	Nice sequence (IZhO18_sequence)	C++17	100 / 100	280 ms	44100 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
long long a[200005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long t;
    cin >> t;
    while (t--)
    {
        long long n, m, k=1;
        cin >> n >> m;
        if (n>m)
        {
            swap(n, m);
            k=-1;
        }
        if (m%n==0)
        {
            cout << m-1 << '\n';
            for (long long i=0; i<m-1; i++)
                cout << -k << ' ';
            cout << '\n';
            continue;
        }
        for (long long i=0; i<n; i++)
            a[i]=0;
        long long g=gcd(n, m), ind=m%n-1, x=0, y=0;
        while (ind!=(m%n-g-1+n)%n)
        {
            a[ind]=1;
            ind=(ind+m%n)%n;
            x++;
        }
        while (ind!=m%n-1)
        {
            a[ind]=-1;
            ind=(ind+m%n)%n;
            y++;
        }
        long long p, q;
        if (g==2)
        {
            for (long long i=min(1000000000LL, (1000000000*x+n-n/g)/y); i>=1; i--)
            {
                if (x==1 || (i*y-n+n/g)%x==1)
                {
                    q=i;
                    break;
                }
            }
            p=(q*y-n+n/g-1)/x;
        }
        else
        {
            for (long long i=min(1000000000LL, 1000000000*x/y); i>=1; i--)
            {
                if (x==1 || i*y%x==1)
                {
                    q=i;
                    break;
                }
            }
            p=(q*y-1)/x;
        }
        cout << n+m-g-1 << '\n';
        for (long long i=0; i<n+m-g-1; i++)
        {
            if (a[i%n]==1)
                cout << p*k << ' ';
            else if (a[i%n]==-1)
                cout << -q*k << ' ';
            else if (g==2 || i%g)
                cout << k << ' ';
            else
                cout << -(g-2)*k << ' ';
        }
        cout << '\n';
    }
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:66:17: warning: 'q' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |             p=(q*y-1)/x;
      |                ~^~

• Subtask 1: 6 / 6
• Subtask 2: 9 / 9
• Subtask 3: 14 / 14
• Subtask 4: 15 / 15
• Subtask 5: 14 / 14
• Subtask 6: 18 / 18
• Subtask 7: 24 / 24