# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
187258 | Ruxandra985 | Alternating Current (BOI18_alternating) | C++14 | 52 ms | 5624 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
pair <int,pair <int,int> > v[DIMN],w[DIMN];
int sol[DIMN] , par[DIMN] , sp1[DIMN] , sp2[DIMN];
set <pair <int,int> > s;
int common (int last , int c){
if (!last)
return 0;
if (v[last].first <= v[last].second.first){
if (v[c].first <= v[c].second.first){
if (v[c].first <= v[last].second.first)
return 1;
return 0;
}
else {
if (v[c].first <= v[last].second.first)
return 1;
return 0;
}
}
else {
if (v[c].first <= v[c].second.first){
if (v[c].first <= v[last].second.first)
return 1;
return 0;
}
else {
if (v[c].second.first > v[last].second.first)
return 1;
return 0;
}
}
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n , m , i , maxi , poz, poz2 , maxi2, last;
fscanf (fin,"%d%d",&n,&m);
maxi = 0;
poz = 0;
for (i=1;i<=m;i++){
fscanf (fin,"%d%d",&v[i].first,&v[i].second.first);
v[i].second.second = i;
w[i] = v[i];
}
maxi2 = 0;
poz2 = 0;
sort (v + 1 , v + m + 1);
for (i=1;i<=m;i++){
if (v[i].first > v[i].second.first && maxi < v[i].second.first){
maxi = v[i].second.first;
poz = i;
}
}
for (i=1;i<=m;i++){
/// check daca i e inclus total in vreun alt interval
if (v[i].first <= v[i].second.first){ /// e un interval normal
if (maxi > v[i].second.first){ /// e inclus
par[i] = poz;
continue;
}
else{
maxi = v[i].second.first;
poz = i;
}
}
else {
maxi = n; /// le tratezi ca pe doua intervale
poz = i;
if (maxi2 > v[i].second.first){ /// e inclus
par[i] = poz2;
continue;
}
else {
maxi2 = v[i].second.first;
poz2 = i;
}
}
par[i] = -1; /// e tata
}
/// daca au ceva in comun, pui semne opuse
last = 0;
for (i=1;i<=m;i++){
if (par[i] == -1){
if (common(last , i)){
sol[v[i].second.second] = 1 - sol[v[last].second.second];
}
else {
sol[v[i].second.second] = 0;
}
last = i;
}
else {
sol[v[i].second.second] = 1 - sol[v[par[i]].second.second];
}
}
for (i=1;i<=m;i++){
if (w[i].first <= w[i].second.first){
if (sol[i] == 1){
sp1[w[i].first]++;
sp1[w[i].second.first+1]--;
}
else {
sp2[w[i].first]++;
sp2[w[i].second.first+1]--;
}
}
else {
if (sol[i] == 1){
sp1[w[i].first]++;
sp1[1]++;
sp1[w[i].second.first+1]--;
}
else {
sp2[w[i].first]++;
sp2[1]++;
sp2[w[i].second.first+1]--;
}
}
}
for (i=1;i<=n;i++){
sp1[i] += sp1[i-1];
sp2[i] += sp2[i-1];
if (!sp1[i] || !sp2[i]){
fprintf (fout,"impossible\n");
return 0;
}
}
for (i=1;i<=m;i++){
fprintf (fout,"%d",sol[i]);
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |