Submission #209336

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
209336	2020-03-13T20:13:02 Z	papa	Spiderman (COCI20_spiderman)	C++14	70 / 70	1320 ms	13404 KB

spiderman

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxv = 1e6;
const int maxn = 3*1e5;
int cnt[maxv + 5];
int p[maxv + 5];
int a[maxn+5];
int k;
int n;
int res[maxn+5];
int res2[maxn+5];

void input()
{
    cin >> n >> k;
    for(int i=1;i<=n;i++) cin >> a[i];
}

void output()
{
    for(int i=1;i<=n;i++) cout << res[i] << " ";
}

void brute()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j) continue;
            if(a[i]%a[j]==k) res2[i]++;
        }
    }
}

int randd(int a,int b)
{
    return a+rand()%(b-a+1);
}

void testprimer()
{
    n = 4000;
    k = randd(0,1e6);
    for(int i=1;i<=n;i++)
    {
        a[i] = randd(1,1e6);
    }
}

bool uporedi()
{
    for(int i=1;i<=n;i++)
        if(res[i]!=res2[i]) return false;

    return true;
}

void razlika()
{
    cout << n << " " << k << "\n";
    for(int i=1;i<=n;i++)
    {
        cout << a[i] << " ";
    }
    cout << "\n";
    cout << "Resi" << "\n";
    for(int i=1;i<=n;i++)
    {
        cout << res[i] << " ";
    }
    cout << "\n";
    cout << "Brute" << "\n";
    for(int i=1;i<=n;i++)
    {
        cout << res2[i] << " ";
    }
    cout << "\n";
    exit(0);
}

int resi(int x)
{
    int rs = 0;
    for(int i=1;i*i<=x;i++)
    {
        if(x%i==0)
        {
            int d1 = i;
            int d2 = x/i;
            if(d1==d2)
            {
                rs+=(d1 > k) ? cnt[d1] : 0;
            }
            else
            {
                rs+=(d1 > k) ? cnt[d1] : 0;
                rs+=(d2 > k) ? cnt[d2] : 0;
            }
        }
    }

    return rs;
}

void resii()
{
    for(int i=1;i<=n;i++)
        cnt[a[i]]++;

    p[maxv] = cnt[maxv];

    for(int i=maxv-1;i>=1;i--) p[i] = p[i+1] + cnt[i];

    for(int i=1;i<=n;i++)
    {
        if(a[i] < k)
        {
            res[i] = 0;
            continue;
        }

        if(a[i]==k)
        {
            res[i] = p[a[i]+1];
            continue;
        }

        cnt[a[i]]--;
        res[i] = resi(a[i]-k);
        cnt[a[i]]++;
    }
}

void restart()
{
    for(int i=1;i<=n;i++) res[i]=res2[i] = 0;
    for(int i=1;i<=maxv;i++) cnt[i]=0;
}

void testiraj()
{
    int brprim = 20;
    for(int i=1;i<=brprim;i++)
    {
        restart();
        testprimer();
        brute();
        resii();
        if(!uporedi())
        {
            razlika();
        }
        else
        {
            cout << "OK" << "\n";
        }
    }
}


void r()
{
    input();
    resii();
    output();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cerr.tie(0);

    bool tt = 0;

    if(tt) testiraj();
    else r();

    return 0;
}

Subtask #1

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	6648 KB	Output is correct
2	Correct	14 ms	5752 KB	Output is correct
3	Correct	346 ms	8488 KB	Output is correct
4	Correct	986 ms	11768 KB	Output is correct
5	Correct	389 ms	9852 KB	Output is correct
6	Correct	1145 ms	13404 KB	Output is correct
7	Correct	440 ms	9848 KB	Output is correct
8	Correct	456 ms	9892 KB	Output is correct
9	Correct	1320 ms	13304 KB	Output is correct
10	Correct	1299 ms	13212 KB	Output is correct