CSES - Datatähti Open 2017 - Results
Submission details
Task:Family reunion
Sender:nigus
Submission time:2017-01-20 01:20:16 +0200
Language:C++
Status:READY
Result:19
Feedback
groupverdictscore
#1UNKNOWN0
#2UNKNOWN0
#3UNKNOWN0
Test results
testverdicttimegroup
#1UNKNOWN--1details
#2UNKNOWN--2details
#3UNKNOWN--3details

Compiler report

input/code.cpp: In function 'll has2(std::vector<long long int>)':
input/code.cpp:143:8: warning: unused variable 'ans' [-Wunused-variable]
     ll ans = 0;
        ^
input/code.cpp: In function 'int main()':
input/code.cpp:171:14: warning: unused variable 'c3' [-Wunused-variable]
     ll c1,c2,c3,c4,c5;
              ^
input/code.cpp:171:17: warning: unused variable 'c4' [-Wunused-variable]
     ll c1,c2,c3,c4,c5;
                 ^
input/code.cpp:171:20: warning: unused variable 'c5' [-Wunused-variable]
     ll c1,c2,c3,c4,c5;
                    ^
input/code.cpp:172:10: warning: unused variable 'b' [-Wunused-variable]
     ll a,b,c;
          ^
input/code.cpp:172:12: warning: unused variable 'c' [-Wunused-variable]
     ll a,b,c;
            ^

Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll mod = 1000000007ll;
ll n,m,k,x,y;

map<ll,ll> M;
ll FAC[10] = {0};

vector<vector<ll> > CP(100001 , vector<ll>());
vector<vector<ll> > C(100001 , vector<ll>());
ll deg[100001] = {0};

vector<ll> COL;


string alf = "ABC";

ll has(vector<ll> P){
ll ans = 0;
for(ll c1 = 0; c1 < k; c1++){
    ans *= k;
    ans += P[c1];
}
return ans;
}

void setup(){
ll t = 1;
for(ll c1 = 0; c1 <= k; c1++){
    FAC[c1] = t;
    t *= (c1+1);
}
vector<ll> P;
for(ll c1 = 0; c1 < k; c1++){
    P.push_back(c1);
}

for(ll c1 = 0; c1 < FAC[k]; c1++){
    ll h = has(P);
    M[h] = c1;
    for(ll c2 = 0; c2 < k; c2++){
        CP[c1].push_back(P[c2]);
        COL.push_back(-1);
    }
    next_permutation(P.begin() , P.end());
}

for(ll c1 = 0; c1 < FAC[k]; c1++){
    vector<ll> Q;
    ll one = CP[c1][0];
    for(ll c2 = 1; c2 < k; c2++){
        if(CP[c1][c2] > one){
            Q.push_back(CP[c1][c2]-1);
        }
        else{
            Q.push_back(CP[c1][c2]);
        }
    }
    Q.push_back(-1);
    for(ll c2 = 0; c2 < k; c2++){
        for(ll c3 = 0; c3 < k-1; c3++){
            if(Q[c3] >= c2)Q[c3]++;
        }
        Q[k-1] = c2;
        ll b = M[has(Q)];
        if(c1 != b){
            C[c1].push_back(b);
            C[b].push_back(c1);
            deg[c1]++;
            deg[b]++;
        }
        for(ll c3 = 0; c3 < k-1; c3++){
            if(Q[c3] >= c2)Q[c3]--;
        }
    }
}

/*
for(ll c1 = 0; c1 < FAC[k]; c1++){
    cout << deg[c1] << "  d\n";
    for(ll c2 = 0; c2 < deg[c1]; c2++){
        ll a = C[c1][c2];
        for(ll c3 = 0; c3 < k; c3++){
            cout << CP[a][c3];
        }cout << " ";
    }cout << "\n";
}
*/

}

bool dfs(ll i, ll d){
    bool mark[3] = {0};
    ll nc = 0;
    vector<ll> ind;
    for(ll c1 = 0; c1 < deg[i]; c1++){
        ind.push_back(c1);
        ll a = C[i][c1];
        if(COL[a] != -1){
            if(mark[COL[a]] == 0)nc++;
            mark[COL[a]] = 1;
        }
    }
    if(d == 0)return (nc<3);
    random_shuffle(ind.begin() , ind.end());

    for(ll c1 = 0; c1 < 3; c1++){
        if(mark[c1] == 0){
            COL[i] = c1;
            bool an = 1;
            for(ll c2 = 0; c2 < deg[i]; c2++){
                ll a = C[i][ind[c2]];
                if(COL[a] == -1){
                    an &= dfs(a,d-1);
                }
            }
            if(an == 1)return an;
        }
    }
    COL[i] = -1;
    return 0;
}

ll has1(vector<ll> P){
    ll ans = 0;
    vector<ll> Q;
    for(ll c1 = 0; c1 < k; c1++){
        Q.push_back(P[c1]);
    }
    for(ll c1 = 0; c1 < k; c1++){
        ans ^= ((Q[c1]+1)%2);
        for(ll c2 = c1+1; c2 < k; c2++){
            Q[c2]-=Q[c1];
        }
    }
    return ans;
}

ll has2(vector<ll> P){
    ll ans = 0;
    vector<ll> Q;
    vector<ll> Q2;
    vector<ll> res;
    for(ll c1 = 0; c1 < k; c1++){
        Q.push_back(P[c1]);
        Q2.push_back(P[c1]);
        res.push_back(0);
    }
    sort(Q2.begin() , Q2.end());

    for(ll c1 = 0; c1 < k; c1++){
        for(ll c2 = 0; c2 < k; c2++){
            if(Q2[c1] == Q[c2]){
                res[c2] = c1;
                break;
            }
        }
    }
    return M[has(res)];
}


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

    ll c1,c2,c3,c4,c5;
    ll a,b,c;
    ll k1;
    cin >> n >> m >> k1;

    if(n == 16 && m == 1 && k1 == 7){

        vector<ll> A;
        ll one = 0;
        for(c1 = 0; c1 < 2*k1+1; c1++){
            cin >> a;
            A.push_back(a);
            if(a == 1)one = c1+1;
        }
        ll i;
        if(k1+1 >= one){
            i = k1+1-one;
        }
        if(k1+1 < one){
            i = n-(one-k1-1);
        }

        //cout << i << " " << one << "\n";

        if(i == 0){cout << "C\n";}
        else{
            if(i%2 == 0)cout << "A\n";
            if(i%2 == 1)cout << "B\n";
        }
    }
    else{
        k = 7;
        setup();
        COL[0] = 0;
        for(c1 = 0; c1 < deg[0]; c1++){
            a = C[0][c1];
            if(a != 0){
                COL[a] = 2;
            }
        }
        for(c1 = 0; c1 < FAC[k]; c1++){
            if(COL[c1] == -1){
                dfs(c1,4);
            }
            //if(COL[c1] == -1){
               // COL[c1] = rand()%3;
           // }
        }

        for(c1 = 0; c1 < FAC[k]; c1++){
            if(COL[c1] == -1){
                dfs(c1,4);
            }
            if(COL[c1] == -1){
                COL[c1] = rand()%3;
            }
        }

        for(c1 = 0; c1 < m; c1++){
            vector<ll> A;
            if(k1 == 3){
                for(c2 = 0; c2 < 7; c2++){
                    cin >> a;
                    A.push_back(a);
                }
            }
            else{
                for(c2 = 0; c2 < 2*k1+1; c2++){
                    cin >> a;
                    if(abs(k1-c2) <= 3){
                        A.push_back(a);
                    }
                }
            }

            ll h = has2(A);
            //cout << h << "\n";
            if(h == 0){
                cout << alf[has1(A)] << "\n";
            }
            else{
                cout << alf[COL[h]] << "\n";
            }

        }

    }
    return 0;
}

Test details

Test 1

Group: 1

Verdict: UNKNOWN

input
#!/bin/bash
set -e
OFFSET=$(grep -onam1 '^__DATA_...

correct output
50

user output
(not available)

Test 2

Group: 2

Verdict: UNKNOWN

input
#!/bin/bash
set -e
OFFSET=$(grep -onam1 '^__DATA_...

correct output
50

user output
(not available)

Test 3

Group: 3

Verdict: UNKNOWN

input
#!/bin/bash
set -e
OFFSET=$(grep -onam1 '^__DATA_...

correct output
50

user output
(not available)