Submission #232693

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
232693	2020-05-17T20:41:47 Z	duality	Stray Cat (JOI20_stray)	C++14	100 / 100	73 ms	17124 KB

#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------
#include "Anthony.h"

vpii adjList[20000];
int dist[20000];
queue<int> Q;
vi m;
string s = "010011";
int doDFS(int u,int p,int pp,int c) {
    int i;
    int x = 0;
    if (p != -1) m[pp] = s[c]-'0';
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i].first;
        if (v != p) x++;
    }
    if (x == 1) {
        for (i = 0; i < adjList[u].size(); i++) {
            int v = adjList[u][i].first;
            if (v != p) doDFS(v,u,adjList[u][i].second,(c+1) % 6);
        }
    }
    else {
        for (i = 0; i < adjList[u].size(); i++) {
            int v = adjList[u][i].first;
            if (v != p) doDFS(v,u,adjList[u][i].second,(s[c]-'0')^1);
        }
    }
    return 0;
}
vector<int> Mark(int N,int M,int A,int B,vector<int> U,vector<int> V) {
    int i;
    for (i = 0; i < M; i++) {
        adjList[U[i]].pb(mp(V[i],i));
        adjList[V[i]].pb(mp(U[i],i));
    }
    if (A >= 3) {
        for (i = 0; i < N; i++) dist[i] = -1;
        Q.push(0),dist[0] = 0;
        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();

            for (i = 0; i < adjList[u].size(); i++) {
                int v = adjList[u][i].first;
                if (dist[v] == -1) {
                    dist[v] = dist[u]+1;
                    Q.push(v);
                }
            }
        }
        for (i = 0; i < M; i++) {
            if (dist[U[i]] == dist[V[i]]) m.pb(dist[U[i]] % 3);
            else m.pb(min(dist[U[i]],dist[V[i]]) % 3);
        }
    }
    else {
        m.resize(M);
        doDFS(0,-1,-1,0);
    }

    return m;
}

#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------
#include "Catherine.h"

int a,b;
void Init(int A,int B) {
    a = A,b = B;
}
vi v;
int f = 1;
int Move(vector<int> y) {
    if (a >= 3) {
        if ((y[1] == 0) && (y[2] == 0)) return 0;
        else if ((y[0] == 0) && (y[2] == 0)) return 1;
        else if ((y[0] == 0) && (y[1] == 0)) return 2;
        else if (y[0] == 0) return 1;
        else if (y[1] == 0) return 2;
        else return 0;
    }
    else {
        if (v.empty()) {
            if (y[0]+y[1] == 2) {
                if (y[0] > 0) y[0]--,v.pb(0);
                else y[1]--,v.pb(1);
                if (y[0] > 0) v.pb(0);
                else v.pb(1);
                return v[1];
            }
            else {
                f = 0;
                if (y[0] == 1) v.pb(0);
                else v.pb(1);
                return v[0];
            }
        }
        else {
            if (f) {
                if (y[0]+y[1] == 1) {
                    if (y[0] == 1) v.pb(0);
                    else v.pb(1);
                    if (v.size() == 5) {
                        string s;
                        int i;
                        for (i = 0; i < v.size(); i++) s += '0'+v[i];
                        if ((s == "11010") || (s == "10100") || (s == "01001") \
                            || (s == "10011") || (s == "00110") || (s == "01101")) {

                            f = 0;
                            v = vi(1,v[3]);
                            return -1;
                        }
                        else {
                            f = 0;
                            return v.back();
                        }
                    }
                    else return v.back();
                }
                else {
                    if ((y[0] == 0) || (y[1] == 0)) {
                        f = 0;
                        v = vi(1,v.back());
                        return -1;
                    }
                    else {
                        f = 0;
                        v.pb(v.back()^1);
                        return v.back();
                    }
                }
            }
            else {
                if (y[0]+y[1] == 1) {
                    if (y[0] == 1) v.pb(0);
                    else v.pb(1);
                    return v.back();
                }
                else {
                    v.pb(v.back()^1);
                    return v.back();
                }
            }
        }
    }
}

Compilation message

Anthony.cpp: In function 'int doDFS(int, int, int, int)':
Anthony.cpp:68:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
Anthony.cpp:73:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < adjList[u].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~
Anthony.cpp:79:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < adjList[u].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~
Anthony.cpp: In function 'std::vector<int> Mark(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:99:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (i = 0; i < adjList[u].size(); i++) {
                         ~~^~~~~~~~~~~~~~~~~~~

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:98:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         for (i = 0; i < v.size(); i++) s += '0'+v[i];
                                     ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	15740 KB	Output is correct
2	Correct	9 ms	1536 KB	Output is correct
3	Correct	45 ms	15096 KB	Output is correct
4	Correct	67 ms	17000 KB	Output is correct
5	Correct	68 ms	17124 KB	Output is correct
6	Correct	53 ms	15616 KB	Output is correct
7	Correct	54 ms	15492 KB	Output is correct
8	Correct	60 ms	16284 KB	Output is correct
9	Correct	67 ms	16288 KB	Output is correct

Subtask #2
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	15740 KB	Output is correct
2	Correct	9 ms	1536 KB	Output is correct
3	Correct	45 ms	15096 KB	Output is correct
4	Correct	67 ms	17000 KB	Output is correct
5	Correct	68 ms	17124 KB	Output is correct
6	Correct	53 ms	15616 KB	Output is correct
7	Correct	54 ms	15492 KB	Output is correct
8	Correct	60 ms	16284 KB	Output is correct
9	Correct	67 ms	16288 KB	Output is correct
10	Correct	50 ms	13712 KB	Output is correct
11	Correct	51 ms	13728 KB	Output is correct
12	Correct	51 ms	13732 KB	Output is correct
13	Correct	49 ms	13704 KB	Output is correct
14	Correct	51 ms	13944 KB	Output is correct
15	Correct	55 ms	14320 KB	Output is correct
16	Correct	57 ms	16488 KB	Output is correct

Subtask #3
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	53 ms	13444 KB	Output is correct
2	Correct	9 ms	1536 KB	Output is correct
3	Correct	44 ms	12984 KB	Output is correct
4	Correct	61 ms	14824 KB	Output is correct
5	Correct	64 ms	14708 KB	Output is correct
6	Correct	52 ms	13556 KB	Output is correct
7	Correct	51 ms	13580 KB	Output is correct
8	Correct	56 ms	14104 KB	Output is correct
9	Correct	56 ms	14068 KB	Output is correct
10	Correct	55 ms	13872 KB	Output is correct
11	Correct	54 ms	13952 KB	Output is correct
12	Correct	56 ms	13848 KB	Output is correct
13	Correct	56 ms	13692 KB	Output is correct
14	Correct	56 ms	14100 KB	Output is correct
15	Correct	57 ms	14120 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	53 ms	13444 KB	Output is correct
2	Correct	9 ms	1536 KB	Output is correct
3	Correct	44 ms	12984 KB	Output is correct
4	Correct	61 ms	14824 KB	Output is correct
5	Correct	64 ms	14708 KB	Output is correct
6	Correct	52 ms	13556 KB	Output is correct
7	Correct	51 ms	13580 KB	Output is correct
8	Correct	56 ms	14104 KB	Output is correct
9	Correct	56 ms	14068 KB	Output is correct
10	Correct	55 ms	13872 KB	Output is correct
11	Correct	54 ms	13952 KB	Output is correct
12	Correct	56 ms	13848 KB	Output is correct
13	Correct	56 ms	13692 KB	Output is correct
14	Correct	56 ms	14100 KB	Output is correct
15	Correct	57 ms	14120 KB	Output is correct
16	Correct	47 ms	11788 KB	Output is correct
17	Correct	46 ms	11776 KB	Output is correct
18	Correct	50 ms	11828 KB	Output is correct
19	Correct	47 ms	12064 KB	Output is correct
20	Correct	53 ms	12408 KB	Output is correct
21	Correct	51 ms	12176 KB	Output is correct
22	Correct	56 ms	14288 KB	Output is correct
23	Correct	49 ms	11960 KB	Output is correct
24	Correct	51 ms	11916 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	1792 KB	Output is correct
2	Correct	9 ms	1536 KB	Output is correct
3	Correct	10 ms	1792 KB	Output is correct
4	Correct	11 ms	1796 KB	Output is correct
5	Correct	10 ms	1792 KB	Output is correct
6	Correct	10 ms	1792 KB	Output is correct
7	Correct	10 ms	1792 KB	Output is correct
8	Correct	10 ms	1792 KB	Output is correct
9	Correct	11 ms	1792 KB	Output is correct
10	Correct	10 ms	1792 KB	Output is correct
11	Correct	10 ms	1796 KB	Output is correct
12	Correct	10 ms	1548 KB	Output is correct
13	Correct	10 ms	1536 KB	Output is correct
14	Correct	10 ms	1792 KB	Output is correct
15	Correct	10 ms	1792 KB	Output is correct
16	Correct	10 ms	1792 KB	Output is correct
17	Correct	10 ms	1536 KB	Output is correct
18	Correct	10 ms	1536 KB	Output is correct
19	Correct	11 ms	1792 KB	Output is correct
20	Correct	10 ms	1536 KB	Output is correct
21	Correct	10 ms	1536 KB	Output is correct
22	Correct	10 ms	1536 KB	Output is correct
23	Correct	10 ms	1792 KB	Output is correct
24	Correct	10 ms	1536 KB	Output is correct
25	Correct	10 ms	1280 KB	Output is correct
26	Correct	10 ms	1536 KB	Output is correct
27	Correct	10 ms	1792 KB	Output is correct
28	Correct	10 ms	1536 KB	Output is correct

Subtask #6
71.0 / 71.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	11604 KB	Output is correct
2	Correct	54 ms	12480 KB	Output is correct
3	Correct	9 ms	1536 KB	Output is correct
4	Correct	42 ms	11320 KB	Output is correct
5	Correct	59 ms	13636 KB	Output is correct
6	Correct	62 ms	13556 KB	Output is correct
7	Correct	60 ms	12744 KB	Output is correct
8	Correct	49 ms	12780 KB	Output is correct
9	Correct	59 ms	13608 KB	Output is correct
10	Correct	61 ms	13636 KB	Output is correct
11	Correct	60 ms	13644 KB	Output is correct
12	Correct	59 ms	13936 KB	Output is correct
13	Correct	66 ms	13628 KB	Output is correct
14	Correct	62 ms	13612 KB	Output is correct
15	Correct	73 ms	13640 KB	Output is correct
16	Correct	60 ms	13640 KB	Output is correct
17	Correct	56 ms	13384 KB	Output is correct
18	Correct	54 ms	13300 KB	Output is correct
19	Correct	55 ms	13268 KB	Output is correct
20	Correct	57 ms	13272 KB	Output is correct
21	Correct	56 ms	13520 KB	Output is correct
22	Correct	59 ms	13380 KB	Output is correct
23	Correct	48 ms	11624 KB	Output is correct
24	Correct	49 ms	11620 KB	Output is correct
25	Correct	50 ms	11844 KB	Output is correct
26	Correct	49 ms	11840 KB	Output is correct
27	Correct	54 ms	12608 KB	Output is correct
28	Correct	63 ms	12520 KB	Output is correct
29	Correct	55 ms	12596 KB	Output is correct
30	Correct	55 ms	12588 KB	Output is correct
31	Correct	47 ms	11516 KB	Output is correct
32	Correct	52 ms	11636 KB	Output is correct
33	Correct	48 ms	11828 KB	Output is correct
34	Correct	49 ms	11832 KB	Output is correct
35	Correct	55 ms	12524 KB	Output is correct
36	Correct	54 ms	12524 KB	Output is correct
37	Correct	55 ms	12412 KB	Output is correct
38	Correct	53 ms	12512 KB	Output is correct
39	Correct	53 ms	12528 KB	Output is correct
40	Correct	54 ms	12284 KB	Output is correct
41	Correct	59 ms	12976 KB	Output is correct
42	Correct	55 ms	12888 KB	Output is correct
43	Correct	56 ms	12968 KB	Output is correct
44	Correct	56 ms	12956 KB	Output is correct
45	Correct	55 ms	12968 KB	Output is correct
46	Correct	55 ms	12924 KB	Output is correct
47	Correct	52 ms	12316 KB	Output is correct
48	Correct	53 ms	12252 KB	Output is correct
49	Correct	51 ms	12308 KB	Output is correct
50	Correct	54 ms	12408 KB	Output is correct
51	Correct	50 ms	11704 KB	Output is correct
52	Correct	49 ms	11704 KB	Output is correct
53	Correct	48 ms	11692 KB	Output is correct
54	Correct	48 ms	11548 KB	Output is correct
55	Correct	50 ms	11700 KB	Output is correct
56	Correct	49 ms	11708 KB	Output is correct
57	Correct	48 ms	11732 KB	Output is correct
58	Correct	50 ms	11708 KB	Output is correct
59	Correct	49 ms	11728 KB	Output is correct
60	Correct	50 ms	11644 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	11620 KB	Output is correct
2	Correct	65 ms	12472 KB	Output is correct
3	Correct	9 ms	1536 KB	Output is correct
4	Correct	42 ms	11572 KB	Output is correct
5	Correct	57 ms	14148 KB	Output is correct
6	Correct	60 ms	14008 KB	Output is correct
7	Correct	50 ms	13020 KB	Output is correct
8	Correct	50 ms	13248 KB	Output is correct
9	Correct	60 ms	14140 KB	Output is correct
10	Correct	60 ms	14252 KB	Output is correct
11	Correct	59 ms	14148 KB	Output is correct
12	Correct	61 ms	14068 KB	Output is correct
13	Correct	61 ms	14144 KB	Output is correct
14	Correct	61 ms	14120 KB	Output is correct
15	Correct	59 ms	14140 KB	Output is correct
16	Correct	59 ms	14144 KB	Output is correct
17	Correct	57 ms	13760 KB	Output is correct
18	Correct	57 ms	13824 KB	Output is correct
19	Correct	57 ms	13860 KB	Output is correct
20	Correct	61 ms	13892 KB	Output is correct
21	Correct	57 ms	13772 KB	Output is correct
22	Correct	55 ms	13768 KB	Output is correct
23	Correct	47 ms	11856 KB	Output is correct
24	Correct	48 ms	11872 KB	Output is correct
25	Correct	49 ms	12352 KB	Output is correct
26	Correct	50 ms	12344 KB	Output is correct
27	Correct	56 ms	13120 KB	Output is correct
28	Correct	54 ms	13112 KB	Output is correct
29	Correct	56 ms	13080 KB	Output is correct
30	Correct	56 ms	13080 KB	Output is correct
31	Correct	48 ms	12092 KB	Output is correct
32	Correct	49 ms	11860 KB	Output is correct
33	Correct	49 ms	12352 KB	Output is correct
34	Correct	49 ms	12344 KB	Output is correct
35	Correct	53 ms	12768 KB	Output is correct
36	Correct	54 ms	12772 KB	Output is correct
37	Correct	55 ms	12892 KB	Output is correct
38	Correct	55 ms	12756 KB	Output is correct
39	Correct	54 ms	12992 KB	Output is correct
40	Correct	54 ms	12784 KB	Output is correct
41	Correct	55 ms	13480 KB	Output is correct
42	Correct	55 ms	13448 KB	Output is correct
43	Correct	55 ms	13328 KB	Output is correct
44	Correct	61 ms	13460 KB	Output is correct
45	Correct	55 ms	13388 KB	Output is correct
46	Correct	57 ms	13480 KB	Output is correct
47	Correct	54 ms	12812 KB	Output is correct
48	Correct	52 ms	12692 KB	Output is correct
49	Correct	52 ms	12692 KB	Output is correct
50	Correct	53 ms	12796 KB	Output is correct
51	Correct	59 ms	12048 KB	Output is correct
52	Correct	49 ms	12192 KB	Output is correct
53	Correct	49 ms	12400 KB	Output is correct
54	Correct	49 ms	12116 KB	Output is correct
55	Correct	49 ms	12048 KB	Output is correct
56	Correct	49 ms	12060 KB	Output is correct
57	Correct	55 ms	12212 KB	Output is correct
58	Correct	50 ms	12212 KB	Output is correct
59	Correct	52 ms	12332 KB	Output is correct
60	Correct	49 ms	12116 KB	Output is correct

Submission #232693

Compilation message

Subtask #1 2.0 / 2.0

Subtask #2 2.0 / 2.0

Subtask #3 2.0 / 2.0

Subtask #4 9.0 / 9.0

Subtask #5 5.0 / 5.0

Subtask #6 71.0 / 71.0

Subtask #7 9.0 / 9.0

Subtask #1
2.0 / 2.0

Subtask #2
2.0 / 2.0

Subtask #3
2.0 / 2.0

Subtask #4
9.0 / 9.0

Subtask #5
5.0 / 5.0

Subtask #6
71.0 / 71.0

Subtask #7
9.0 / 9.0