oj.uz

답안 #767152

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
767152 2023-06-26T12:49:41 Z DJeniUp 자동 인형 (IOI18_doll) C++17
37 / 100
 692 ms 34128 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

typedef int ll;
typedef pair<ll,ll>pairll;

#define pb push_back
#define fr first
#define sc second

ll h,a[400007],b[400007],f[400007],u[400007];

vector<ll>v[200007];

priority_queue<pairll,vector<pairll>, greater<pairll> >p;

vector<ll>c,x,y;

void create_circuit(int M, std::vector<int> A) {
    A.pb(0);
    for(int i=0;i<A.size();i++){
        v[0].pb(A[i]);
    }
    for(int i=0;i<=M;i++){
        if(v[i].size()==0)c.pb(-1);
        else if(v[i].size()==1)c.pb(v[i][0]);
        else{
            h++;
            x.pb(-h);
            y.pb(-h);
            c.pb(-h);
            for(int j=0;j<v[i].size();j++){
                ll k=-c[i]-1;
                while(1){
                    if(f[k]%2==0){
                        f[k]++;
                        if(x[k]==-k-1){
                            x[k]=v[i][j];
                            break;
                        }else if(x[k]<0){
                            k=-x[k]-1;
                        }else{
                            h++;
                            f[h-1]=1;
                            x.pb(-h);
                            y.pb(-h);
                            x[h-1]=x[k];
                            x[k]=-h;
                            k=h-1;
                        }
                    }else{
                        f[k]++;
                        if(y[k]==-k-1){
                            y[k]=v[i][j];
                            break;
                        }else if(y[k]<0){
                            k=-y[k]-1;
                        }else{
                            h++;
                            f[h-1]=1;
                            x.pb(-h);
                            y.pb(-h);
                            x[h-1]=y[k];
                            y[k]=-h;
                            k=h-1;
                        }
                    }
                }
            }
        }
    }
    while(1){
        ll k=c[0];
        ll z=0;
        ll r=0;
        for(int i=0;i<h;i++){
            f[i]=0;
            u[i]=0;
        }
        while(p.size()>0)p.pop();
        ll pr=0;
        while(k!=0){
                r++;
            pr=k;
            if(k>0){
                k=c[k];
            }else{
                if(u[-k-1]==0)u[-k-1]=r;
                if(f[-k-1]%2==0){
                    p.push({u[-k-1],k});
                    f[-k-1]++;
                    k=x[-k-1];
                }else{

                    f[-k-1]++;
                    k=y[-k-1];
                }
            }
        }
        //cout<<p.back()<<" "<<f[-p.back()-1]<<endl;
        while(p.size()>0 && f[-p.top().sc-1]%2==0)p.pop();
        if(p.size()==0)break;
        while(p.size()>0){
            while(p.size()>0 && f[-p.top().sc-1]%2==0)p.pop();
            if(p.size()==0)break;
            z=p.top().sc;
            p.pop();
            //cout<<z<<endl;
            if(f[-z-1]%2==0){
                break;
            }else{
                if(pr>0)c[pr]=z;
                else{
                    if(f[-pr-1]%2==1)x[-pr-1]=z;
                    else y[-pr-1]=z;
                }
                k=-z-1;
                while(1){
                    pr=-k-1;
                    if(f[k]%2==0){
                        p.push({u[k],-k-1});
                        f[k]++;
                        if(x[k]==-k-1){
                            x[k]=0;
                            break;
                        }else if(x[k]<0){
                            k=-x[k]-1;
                        }else{
                            h++;
                            f[h-1]=1;
                            x.pb(-h);
                            y.pb(-h);
                            x[h-1]=x[k];
                            x[k]=-h;
                            k=h-1;
                        }
                    }else{
                        f[k]++;
                        if(y[k]==-k-1){
                            y[k]=0;
                            break;
                        }else if(y[k]<0){
                            k=-y[k]-1;
                        }else{
                            h++;
                            f[h-1]=1;
                            x.pb(-h);
                            y.pb(-h);
                            x[h-1]=y[k];
                            y[k]=-h;
                            k=h-1;
                        }
                    }
                }
            }
        }
    }
    //cout<<c.size()<<" "<<x.size()<<" "<<y.size()<<endl;
    for(int i=0;i<=M;i++){
       // cout<<i<<" "<<c[i]<<endl;
    }
    for(int i=0;i<x.size();i++){
       //if(x[i]==-i-1)swap(x[i],y[i]);
       //cout<<-i-1<<" "<<x[i]<<" "<<y[i]<<endl;
    }
    if(h>2*A.size()-2)exit(1);
    answer(c,x,y);
    return ;
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<A.size();i++){
      |                 ~^~~~~~~~~
doll.cpp:33:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |             for(int j=0;j<v[i].size();j++){
      |                         ~^~~~~~~~~~~~
doll.cpp:163:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     for(int i=0;i<x.size();i++){
      |                 ~^~~~~~~~~
doll.cpp:167:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |     if(h>2*A.size()-2)exit(1);
      |        ~^~~~~~~~~~~~~

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 2 ms 4948 KB Output is partially correct
2 Partially correct 446 ms 28580 KB Output is partially correct
3 Partially correct 462 ms 28244 KB Output is partially correct
4 Partially correct 670 ms 32592 KB Output is partially correct

Subtask #6
28.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 2 ms 4948 KB Output is partially correct
2 Partially correct 446 ms 28580 KB Output is partially correct
3 Partially correct 462 ms 28244 KB Output is partially correct
4 Partially correct 670 ms 32592 KB Output is partially correct
5 Partially correct 677 ms 34128 KB Output is partially correct
6 Partially correct 692 ms 33772 KB Output is partially correct
7 Partially correct 670 ms 33728 KB Output is partially correct
8 Partially correct 655 ms 33448 KB Output is partially correct
9 Partially correct 444 ms 28244 KB Output is partially correct
10 Partially correct 681 ms 33228 KB Output is partially correct
11 Partially correct 688 ms 33028 KB Output is partially correct
12 Partially correct 449 ms 28428 KB Output is partially correct
13 Partially correct 479 ms 29980 KB Output is partially correct
14 Partially correct 467 ms 28956 KB Output is partially correct
15 Partially correct 472 ms 29072 KB Output is partially correct
16 Partially correct 12 ms 5636 KB Output is partially correct
17 Correct 228 ms 26264 KB Output is correct
18 Partially correct 468 ms 28748 KB Output is partially correct
19 Partially correct 460 ms 28424 KB Output is partially correct
20 Partially correct 689 ms 33228 KB Output is partially correct
21 Partially correct 669 ms 32932 KB Output is partially correct
22 Partially correct 667 ms 32972 KB Output is partially correct