QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #446706 | #6386. Dolls | giorgi_pkhaladze | 0 | 0ms | 3652kb | C++20 | 796b | 2024-06-17 15:21:04 | 2024-06-17 15:21:05 |
answer
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define ss second
#define ff first
#define pb push_back
using namespace std;
int n,m,k,i,j,used[100005],a[100005],p[100005],sz[100005];
int find_set(int o){
if(p[o]==o)return o;
else return find_set(p[o]);
}
void union_set(int x, int y){
int px=find_set(x);
int py=find_set(y);
if(px==0 || py==0)return;
if(sz[px]>sz[py]){p[py]=px; sz[px]+=sz[py];}
else {p[px]=py; sz[py]+=sz[px];}
}
int main() {
cin>>n;
int ans=0;
for(k=1; k<=n; k++){
cin>>a[k];
if(find_set(a[k])){cout<<ans<<" "; continue;}
p[a[k]]=a[k],sz[a[k]]=1;
if(sz[find_set(a[k]-1)]%2==sz[find_set(a[k]+1)]%2 && sz[find_set(a[k]-1)]%2==0)ans++;
union_set(a[k]-1,a[k]); union_set(a[k+1],a[k]); cout<<ans<<" ";
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3652kb
input:
190 57 94 24 27 110 44 72 82 55 7 9 43 22 86 95 84 125 16 75 28 46 10 14 131 112 132 33 53 103 139 118 126 137 13 140 77 25 23 47 116 68 150 81 97 165 58 88 63 42 89 123 11 113 83 124 130 80 35 143 155 153 48 8 136 104 101 90 37 21 99 142 34 64 115 109 26 92 144 61 51 114 49 148 96 60 30 54 134 141 ...
output:
1 2 3 4 5 6 7 8 9 10 11 11 12 13 13 14 15 16 17 17 18 18 19 20 21 21 22 23 24 25 26 26 27 27 27 28 28 28 28 29 30 31 31 32 33 33 34 35 35 35 36 37 37 37 37 38 38 39 40 41 42 43 43 43 43 44 45 46 47 48 48 48 48 48 48 49 50 50 51 52 52 52 53 53 53 54 54 55 55 56 56 57 57 58 58 58 59 59 59 60 60 61 61 ...
result:
wrong answer 1st lines differ - expected: '1 2 3 4 5 6 7 8 9 10 11 11 12 ...7 77 77 77 77 77 77 77 77 77 77', found: '1 2 3 4 5 6 7 8 9 10 11 11 12 ... 70 70 70 70 70 70 70 70 70 70 '
Subtask #2:
score: 0
Runtime Error
Test #22:
score: 0
Runtime Error
input:
3922 1195 63679 1195 96797 63679 60311 456263 228361 96797 270167 60311 169529 60311 60311 456263 270167 169529 375829 169529 169529 270167 375829 60311 228361 1195 375829 96797 375829 375829 96797 375829 169529 456263 375829 1195 375829 456263 96797 169529 228361 63679 270167 212365 456263 270167 9...
output:
1 2 2 3 3 4
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%