Submission #377763
Source Code Expand
#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>
using namespace std;
#define reE(i,a,b) for(auto (i)=(a);(i)<=(b);(i)++)
#define rE(i,b) reE(i,0,b)
#define reT(i,a,b) for(auto (i)=(a);(i)<(b);(i)++)
#define rT(i,b) reT(i,0,b)
#define rep(i,a,b) reE(i,a,b);
#define rev(i,a,b) for(auto (i)=(b)-1;(i)>=(a);(i)--)
#define itr(i,b) for(auto (i)=(b).begin();(i)!=(b).end();++(i))
#define LL long long
#define all(b) (b).begin(),(b).end()
#define input_init stringstream ss; string strtoken, token; istringstream is
#define input_line getline(cin, strtoken);is.str(strtoken);is.clear(istringstream::goodbit)
#define input_token(num) ss.str(""); ss.clear(stringstream::goodbit); getline(is, token, ','); ss << token; ss >> num
typedef complex<double> P;
typedef vector<P> Poly;
const LL INF = 1 << 30;
const double eps = 1e-8;
int T;
vector<list<int>> adj;
vector<string> a;
map<string,int> memo;
vector<int> color;
void construct_adj(){
rT(i,T){
if(memo.count(a[i])>0)continue;
//cout<<a[i]<<endl;
int v=(int)adj.size();
adj.push_back(list<int>());
reT(j,1,10){
swap(a[i][j],a[i][j-1]);
if(memo.count(a[i])>0){
//cout<<"-"<<a[i]<<endl;
int u=memo[a[i]];
adj[v].push_back(u);
adj[u].push_back(v);
}
swap(a[i][j],a[i][j-1]);
}
memo[a[i]]=v;
}
}
void coloring(){
color.resize(adj.size());
for(auto &c:color)c=-1;
queue<int> q;
rT(i,(int)adj.size()){
if(color[i]==-1){
color[i]=0;
q.push(i);
while(q.empty()==false){
int v=q.front();q.pop();
for(auto &u:adj[v]){
if(color[u]==-1){
color[u]=color[v]^1;
q.push(u);
}
}
}
}
}
}
int main(void){
cin>>T;
a.resize(T);
adj.reserve(T);
rT(i,T)cin>>a[i];
construct_adj();
coloring();
for(auto &s:a){
cout<<color[memo[s]]<<endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
F - チェックディジット |
User |
btk15049 |
Language |
C++11 (GCC 4.9.2) |
Score |
200 |
Code Size |
2137 Byte |
Status |
AC |
Exec Time |
873 ms |
Memory |
20084 KB |
Judge Result
Set Name |
Subtask00 |
Subtask01 |
Subtask02 |
Subtask03 |
Subtask04 |
Subtask05 |
Subtask06 |
Subtask07 |
Score / Max Score |
25 / 25 |
25 / 25 |
25 / 25 |
25 / 25 |
25 / 25 |
25 / 25 |
25 / 25 |
25 / 25 |
Status |
|
|
|
|
|
|
|
|
Set Name |
Test Cases |
Subtask00 |
00_n_3e1 |
Subtask01 |
01_n_1e2 |
Subtask02 |
02_n_3e2 |
Subtask03 |
03_n_1e3 |
Subtask04 |
04_n_3e3 |
Subtask05 |
05_n_1e4 |
Subtask06 |
06_n_3e4 |
Subtask07 |
07_n_1e5 |
Case Name |
Status |
Exec Time |
Memory |
00_n_3e1 |
AC |
26 ms |
920 KB |
01_n_1e2 |
AC |
27 ms |
804 KB |
02_n_3e2 |
AC |
27 ms |
920 KB |
03_n_1e3 |
AC |
30 ms |
924 KB |
04_n_3e3 |
AC |
42 ms |
1320 KB |
05_n_1e4 |
AC |
99 ms |
2600 KB |
06_n_3e4 |
AC |
271 ms |
6308 KB |
07_n_1e5 |
AC |
873 ms |
20084 KB |
sample |
AC |
25 ms |
928 KB |