QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#284125 | #5689. 喵了个喵 II | simonG# | WA | 64ms | 12968kb | C++14 | 1.4kb | 2023-12-16 10:29:30 | 2023-12-16 10:29:32 |
Judging History
answer
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<random>
using namespace std;
const int N=2e5+10,mod=998244353;
int n,m,a[N],fa[N];
int val[N],col[N];
vector<int> b;
vector<int> pos[N];
vector<pair<int,int>> g;
int getf(int x) {
if(fa[x]==x) return x;
return fa[x]=getf(fa[x]);
}
bool merge(int x,int y) {
int fx=getf(x),fy=getf(y);
if(fx==fy) return false;
else return fa[fx]=fy,true;
}
int main() {
scanf("%d",&n); n*=4;
for(int i=1; i<=n; i++) scanf("%d",&a[i]),b.push_back(a[i]);
sort(b.begin(),b.end());
m=unique(b.begin(),b.end())-b.begin();
b.resize(m);
for(int i=1; i<=n; i++) {
a[i]=lower_bound(b.begin(),b.end(),a[i])-b.begin()+1;
pos[a[i]].push_back(i);
}
for(int i=1; i<=m; i++) {
int cnt=pos[i].size();
if(cnt&1) return printf("No\n"),0;
for(int j=0; j<cnt; j+=2)
g.push_back({pos[i][j],pos[i][j+1]});
}
sort(g.begin(),g.end());
int num=m,mr=g[0].second;
for(int i=1; i<=m; i++) fa[i]=i;
for(int i=1; i<(int)g.size(); i++) {
if(g[i].first<g[i-1].second) {
if(merge(a[g[i].first],a[g[i-1].first])) num--;
}
if(g[i].second<mr) return printf("No\n"),0;
mr=max(mr,g[i].second);
}
printf("Yes\n");
for(int i=1; i<=m; i++) getf(i);
for(int i=1; i<=n; i++) {
int o=0;
for(int j:pos[i]) {
col[j]=o;
o^=1;
}
}
for(int i=1; i<=n; i++) printf("%d",col[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 58ms
memory: 12852kb
input:
50000 12725 41478 2443 1096 36968 36898 3393 45898 43154 26629 22985 37972 13935 25628 40196 40293 39791 29109 455 45812 12634 21086 8928 13600 25416 30244 15917 22568 35849 40189 27442 28785 46334 25651 7172 30994 39724 27853 47091 21306 42087 31612 22081 23002 17127 15269 11569 8254 41080 30112 31...
output:
Yes 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok correct
Test #2:
score: 0
Accepted
time: 64ms
memory: 12856kb
input:
50000 39298 39298 14319 14319 11620 11620 20424 20424 14345 14345 28478 28478 11587 11587 25545 25545 24607 24607 18203 18203 30593 30593 144 144 2117 2117 14201 14201 27012 27012 20683 20683 39367 39367 7902 7902 12365 12365 17601 17601 29145 29145 15133 15133 47765 47765 22205 22205 13706 13706 20...
output:
Yes 01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...
result:
ok correct
Test #3:
score: 0
Accepted
time: 63ms
memory: 12968kb
input:
50000 21684 21684 49246 49246 20339 20339 12374 12374 25130 25130 30869 30869 21854 21854 19251 19251 24016 24016 4812 4812 13915 13915 14386 14386 33943 33943 43449 43449 16175 16175 29984 29984 4712 4712 48795 48795 952 952 3589 3589 34274 34274 12915 12915 6840 6840 23436 23436 15670 15670 3873 3...
output:
Yes 01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...
result:
ok correct
Test #4:
score: -100
Wrong Answer
time: 51ms
memory: 12468kb
input:
50000 236 236 32031 707 41062 32031 37516 21446 707 41062 37516 21446 26170 44004 47187 26170 9742 44004 47187 9742 14845 835 14845 43803 4270 835 43803 4270 44275 22853 44275 45825 5286 8810 10767 49050 26809 22853 36108 45825 46063 5286 6289 5206 8810 24938 33324 48973 10767 49050 49412 19286 4152...
output:
No
result:
wrong answer Incorrect