Submission #383134

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
383134	2021-03-28T21:50:05 Z	Pichon5	Mechanical Doll (IOI18_doll)	C++17	16 / 100	94 ms	8140 KB

doll

#include "doll.h"
#include<bits/stdc++.h>
#define lcm(a,b) (a/__gcd(a,b))*b
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define F first
#define S second
#define mp make_pair
//salida rapida "\n"
//DECIMALES fixed<<sp(n)<<x<<endl;
//gcd(a,b)= ax + by
//lCB x&-x
//set.erase(it) - ersases the element present at the required index//auto it = s.find(element)
//set.find(element) - iterator pointing to the given element if it is present else return pointer pointing to set.end()
//set.lower_bound(element) - iterator pointing to element greater than or equal to the given element
//set.upper_bound(element) - iterator pointing to element greater than the given element
// | ^
//__builtin_popcount(x)
using namespace std;
void create_circuit(int m,vi A) {
  int n = A.size();
  vi C(m + 1,-1);
  vi vis(m+1,0);
  C[0]=A[0];
  int num=0;
  for(int i=0;i<n;i++)vis[A[i]]++;
  for(int i=1;i<=m;i++){
    if(vis[i]==0)C[i]=0;
    if(vis[i]==2)num++;
    if(vis[i]>=3)num+=3;
  }
  vi X(num),Y(num);
  vi S(m+1,-1);
  vi curr(m+1,1);
  int cnt=1;
  for(int i=0;i<n;i++){
    if(vis[A[i]]==1){
        if(i==n-1){
            C[A[i]]=0;
        }else{
            C[A[i]]=A[i+1];
        }
    }
    if(vis[A[i]]==2){
        if(S[A[i]]==-1){
            S[A[i]]=cnt;
            C[A[i]]=-cnt;
            X[cnt-1]=A[i+1];
            cnt++;
        }else{
            int aux=S[A[i]];
            if(i==n-1){
                Y[aux-1]=0;
            }else{
                Y[aux-1]=A[i+1];
            }
        }
    }
    if(vis[A[i]]==3){
        if(S[A[i]]==-1){
            C[A[i]]=-cnt;
            X[cnt-1]=-(cnt+1);
            X[cnt]=-cnt;
            Y[cnt-1]=-(cnt+2);
            X[cnt+1]=A[i+1];
            S[A[i]]=cnt;
            cnt+=3;
            curr[A[i]]=3;
        }else{
            if(curr[A[i]]==3){
                int aux=S[A[i]];
                Y[aux]=A[i+1];
                curr[A[i]]=4;
            }else{
                int aux=S[A[i]];
                if(i==n-1){
                    Y[aux+1]=0;
                }else{
                    Y[aux+1]=A[i+1];
                }
            }
        }
    }
    if(vis[A[i]]==4){
        if(S[A[i]]==-1){
            S[A[i]]=cnt;
            C[A[i]]=-cnt;
            X[cnt-1]=-(cnt+1);
            Y[cnt-1]=-(cnt+2);
            X[cnt]=A[i+1];
            cnt+=3;
            curr[A[i]]=2;
        }else{
            int aux=S[A[i]];
            if(curr[A[i]]==2){
                X[aux+1]=A[i+1];
            }
            if(curr[A[i]]==3){
                Y[aux]=A[i+1];
            }
            if(curr[A[i]]==4){
                if(i==n-1){
                    Y[aux+1]=0;
                }else{
                    Y[aux+1]=A[i+1];
                }
            }
            curr[A[i]]++;
        }
    }
  }

    /*for(int i=0;i<=m;i++){
        cout<<C[i]<<" ";
    }
    cout<<endl;
    for(int i=0;i<X.size();i++){
        cout<<-(i+1)<<"  "<<X[i]<<" "<<Y[i]<<endl;
    }*/
  answer(C, X, Y);
}
//3 4 1 2 1 3
//4 4 1 2 1 3
//4 10 1 2 1 3 1 2 3 3 4 3
//3 7 2 1 3 2 2 3 1
// la buena 2 5 1 2 2 2 2

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	204 KB	Output is correct
2	Correct	39 ms	3156 KB	Output is correct
3	Correct	22 ms	2380 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	16 ms	2636 KB	Output is correct
6	Correct	32 ms	3360 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	204 KB	Output is correct
2	Correct	39 ms	3156 KB	Output is correct
3	Correct	22 ms	2380 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	16 ms	2636 KB	Output is correct
6	Correct	32 ms	3360 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	64 ms	4396 KB	Output is correct
9	Correct	44 ms	4684 KB	Output is correct
10	Correct	71 ms	6452 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	2 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	204 KB	Output is correct
2	Correct	39 ms	3156 KB	Output is correct
3	Correct	22 ms	2380 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	16 ms	2636 KB	Output is correct
6	Correct	32 ms	3360 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	64 ms	4396 KB	Output is correct
9	Correct	44 ms	4684 KB	Output is correct
10	Correct	71 ms	6452 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	2 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	89 ms	8140 KB	Output is correct
15	Correct	51 ms	4408 KB	Output is correct
16	Correct	72 ms	6504 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	94 ms	7216 KB	Output is correct
21	Correct	1 ms	204 KB	Output is correct
22	Correct	1 ms	204 KB	Output is correct