Submission #22862

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
22862	2017-04-30T07:53:43 Z	Jongwon Party(#988, gs13105)	Window Xor (KRIII5_WX)	C++14	0 / 7	1000 ms	396224 KB

WX

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef vector<int> V;

int n;

V pro(const V &a, const V &b)
{
    V r, t;

    for(const int &x: a)
        for(const int &y: b)
            r.push_back((x+y) % n);

    sort(r.begin(), r.end());

    if(r.size() == 1)
        return r;

    bool c = 0;
    for(int i = 0; i<r.size(); i++)
    {
        if(i != 0 && r[i-1] != r[i])
        {
            if(c)
                t.push_back(r[i-1]);
            c = 1;
        }
        else
            c = !c;
    }
    if(c)
        t.push_back(r[r.size()-1]);

    return t;
}

V exp(const V &a, long long t)
{
    if(t == 1)
        return a;

    if(t%2)
        return pro(exp(a, t-1), a);

    V h = exp(a, t/2);
    return pro(h, h);
}

int arr[100000];
int res[100000];
bool chk[100000];

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    int k, i, j;
    long long t;
    scanf("%d%d%lld", &n, &k, &t);
    for(i = 0; i<n; i++)
        scanf("%d", &arr[i]);

    V a;

    for(i = 0; i<k; i++)
        a.push_back(i);

    a = exp(a, t);

    for(int &x: a)
        chk[x] = 1;

    const int pp = 50;

    V d[pp+1];
    for(j = 1; j<=pp; j++)
    {
        for(i = 0; i<n; i++)
            if(chk[i] ^ chk[(i+j)%n])
                d[j].push_back(i);
    }

    int xx = 1;
    for(j = 2; j<=pp; j++)
        if(d[j].size() < d[xx].size())
            xx = j;

    for(i = 0; i<xx; i++)
        for(int &x: a)
            res[i] ^= arr[(x+i)%n];

    for(i = xx; i<n; i++)
    {
        res[i] = res[i-xx];
        for(int &y: d[xx])
            res[i] ^= arr[(i+y)%n];
    }

    for(i = 0; i<n; i++)
        printf("%d ", res[i]);
    return 0;
}

Compilation message

WX.cpp: In function 'V pro(const V&, const V&)':
WX.cpp:27:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i<r.size(); i++)
                     ^
WX.cpp: In function 'int main()':
WX.cpp:67:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%lld", &n, &k, &t);
                                  ^
WX.cpp:69:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &arr[i]);
                             ^

Subtask #1

0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2812 KB	Output is correct
2	Correct	0 ms	2812 KB	Output is correct
3	Correct	0 ms	2812 KB	Output is correct
4	Correct	49 ms	2812 KB	Output is correct
5	Correct	43 ms	2812 KB	Output is correct
6	Correct	59 ms	2812 KB	Output is correct
7	Correct	53 ms	2812 KB	Output is correct
8	Execution timed out	1000 ms	396224 KB	Execution timed out
9	Halted	0 ms	0 KB	-

Subtask #2

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1000 ms	396208 KB	Execution timed out
2	Halted	0 ms	0 KB	-