Task: | Family reunion |
Sender: | nigus |
Submission time: | 2017-01-20 01:14:36 +0200 |
Language: | C++ |
Status: | READY |
Result: | 19 |
group | verdict | score |
---|---|---|
#1 | UNKNOWN | 0 |
#2 | UNKNOWN | 0 |
#3 | UNKNOWN | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | UNKNOWN | -- | 1 | details |
#2 | UNKNOWN | -- | 2 | details |
#3 | UNKNOWN | -- | 3 | details |
Compiler report
input/code.cpp: In function 'll has2(std::vector<long long int>)': input/code.cpp:145:8: warning: unused variable 'ans' [-Wunused-variable] ll ans = 0; ^ input/code.cpp: In function 'int main()': input/code.cpp:173:14: warning: unused variable 'c3' [-Wunused-variable] ll c1,c2,c3,c4,c5; ^ input/code.cpp:173:17: warning: unused variable 'c4' [-Wunused-variable] ll c1,c2,c3,c4,c5; ^ input/code.cpp:173:20: warning: unused variable 'c5' [-Wunused-variable] ll c1,c2,c3,c4,c5; ^ input/code.cpp:174:10: warning: unused variable 'b' [-Wunused-variable] ll a,b,c; ^ input/code.cpp:174: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){ 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; } } 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); } } if(an == 1)return an; } } COL[i] = -1; if(rand()%50 == 0)COL[i] = rand()%3; 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); } //if(COL[c1] == -1){ // COL[c1] = rand()%3; // } } for(c1 = 0; c1 < FAC[k]; c1++){ if(COL[c1] == -1){ dfs(c1); } 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) |