oj.uz

Submission #931376

# Submission time Handle Problem Language Result Execution time Memory
931376 2024-02-21T16:50:20 Z HuyQuang_re_Zero Mechanical Doll (IOI18_doll) C++14
63.4502 / 100
 98 ms 53328 KB 
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define maxn 1000005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x)
#include "doll.h"
using namespace std;
int s,i,n,m,numa[maxn],numb[maxn],k,num[maxn],a[maxn];
vector <int> res,X,Y,to[maxn];
/*
void answer(vector <int> res,vector <int> X,vector <int> Y)
{
    for(int x:res) cout<<x<<'\n';
    for(int i=0;i<s;i++) cout<<X[i]<<" "<<Y[i]<<'\n';
}*/
struct Graph
{
    int n=0;
    vector <int> X,Y;
    vector <II> sink;
};
Graph cal(int n)
{
    Graph res;
    if(n==2)
    {
        res.n=1;
        res.X.push_back(0); res.X.push_back(-1);
        res.Y.push_back(0); res.Y.push_back(-1);
        res.sink.push_back({ 1,0 });
        res.sink.push_back({ 1,1 });
        return res;
    }
    res.n=1;
    Graph a=cal((n+1)/2),b=a;
    res.X.resize(a.n+b.n+2);
    res.Y.resize(a.n+b.n+2);
    res.X[1]=res.n+1;
    for(int i=1;i<=a.n;i++) numa[i]=++res.n;
    for(int i=1;i<=a.n;i++)
    {
        res.X[numa[i]]=(a.X[i]>-1 ? numa[a.X[i]] : -1);
        res.Y[numa[i]]=(a.Y[i]>-1 ? numa[a.Y[i]] : -1);
    }
    res.Y[1]=res.n+1;
    for(int i=1;i<=b.n;i++) numb[i]=++res.n;
    for(int i=1;i<=b.n;i++)
    {
        res.X[numb[i]]=(b.X[i]>-1 ? numb[b.X[i]] : -1);
        res.Y[numb[i]]=(b.Y[i]>-1 ? numb[b.Y[i]] : -1);
    }
    if(n&1)
    {
        if(b.sink[b.sink.size()-2].snd==0)
            res.X[numb[b.sink[b.sink.size()-2].fst]]=1;
        else res.Y[numb[b.sink[b.sink.size()-2].fst]]=1;

        for(int i=0;i<a.sink.size()-2;i++)
        {
            res.sink.push_back({ numa[a.sink[i].fst],a.sink[i].snd });
            res.sink.push_back({ numb[b.sink[i].fst],b.sink[i].snd });
        }
        res.sink.push_back({ numa[a.sink[a.sink.size()-2].fst],a.sink[a.sink.size()-2].snd });
        res.sink.push_back({ numa[a.sink[a.sink.size()-1].fst],a.sink[a.sink.size()-1].snd });
        res.sink.push_back({ numb[b.sink[b.sink.size()-1].fst],b.sink[b.sink.size()-1].snd });
    }
    else
    {
        for(int i=0;i<a.sink.size();i++)
        {
            res.sink.push_back({ numa[a.sink[i].fst],a.sink[i].snd });
            res.sink.push_back({ numb[b.sink[i].fst],b.sink[i].snd });
        }
    }
    return res;
}
void sub1()
{
    for(k=1;k<=m;k++)
    {
        if(to[k].size()==1)
        {
            res[k]=to[k].back();
            continue;
        }
        if(to[k].size()==0)
        {
            res[k]=0;
            continue;
        }
        Graph G=cal(to[k].size());
        res[k]=-s-1;
        for(i=1;i<=G.n;i++) num[i]=++s;
        for(i=1;i<=G.n;i++)
        {
            X[num[i]-1]=-num[G.X[i]];
            Y[num[i]-1]=-num[G.Y[i]];
        }
        for(i=0;i<to[k].size();i++)
        {
            if(G.sink[i].snd==0)
                X[num[G.sink[i].fst]-1]=to[k][i];
            else Y[num[G.sink[i].fst]-1]=to[k][i];
        }
    }
    while(X.size()>s) X.pop_back();
    while(Y.size()>s) Y.pop_back();
    answer(res,X,Y);
}

void sub2()
{
    Graph G=cal(n);
    for(i=1;i<=m;i++) res[i]=-1;
    for(i=1;i<=G.n;i++)
    {
        X[i-1]=-G.X[i];
        Y[i-1]=-G.Y[i];
    }
    for(i=0;i<G.sink.size();i++)
        if(G.sink[i].snd==0)
            X[G.sink[i].fst-1]=a[i+2];
        else Y[G.sink[i].fst-1]=a[i+2];

    s=G.n;
    while(X.size()>s) X.pop_back();
    while(Y.size()>s) Y.pop_back();
    answer(res,X,Y);
}
void sub_same()
{
    Graph G=cal(n);
    res[m]=-1;
    int G_end=G.sink.back().fst;
    auto check=[&](int k)
    {
        return k!=G_end && G.X[k]==-1 && G.Y[k]==-1;
    };
    for(i=1;i<=G.n;i++)
        if(!check(i)) num[i]=++s;


    if(s!=G.n) s++,X[s-1]=Y[s-1]=1;


  //  cerr<<G.n<<" "<<s<<'\n';
    for(i=1;i<=G.n;i++)
    {
        if(check(i)) continue;
    //    cerr<<i<<'\n';
        if(G.X[i]==-1) X[num[i]-1]=1;
        else if(check(G.X[i])) X[num[i]-1]=-s;
        else X[num[i]-1]=-num[G.X[i]];

        if(G.Y[i]==-1) Y[num[i]-1]=1;
        else if(check(G.Y[i])) Y[num[i]-1]=-s;
        else Y[num[i]-1]=-num[G.Y[i]];
    }
   // cerr<<num[G_end]<<'\n';
    if(G.sink.back().snd==0)
        X[num[G_end]-1]=0;
    else Y[num[G_end]-1]=0;

    while(X.size()>s) X.pop_back();
    while(Y.size()>s) Y.pop_back();
    answer(res,X,Y);
}


void create_circuit(int _m,vector <int> _a)
{
    m=_m; n=_a.size();
    int ok=1;
    for(i=0;i<n;i++)
    {
        a[i+1]=_a[i];
        if(i+1<n) to[_a[i]].push_back(_a[i+1]);
        else to[_a[i]].push_back(0);
    }
    for(i=1;i<=m;i++)
        ok&=(to[i].size()<=4);
    res.resize(m+1);
    res[0]=a[1];
    X.resize(2*n); Y.resize(2*n);
    if(ok) sub1();
    else if(m==1) sub_same();
    else sub2();
}
/*
int main()
{
    freopen("doll.inp","r",stdin);
    freopen("doll.out","w",stdout);
    int m,n,k;
    cin>>m;
    vector <int> a;
    while(cin>>k) a.push_back(k);
    create_circuit(m,a);
}
*/

Compilation message

doll.cpp: In function 'Graph cal(int)':
doll.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for(int i=0;i<a.sink.size()-2;i++)
      |                     ~^~~~~~~~~~~~~~~~
doll.cpp:81:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for(int i=0;i<a.sink.size();i++)
      |                     ~^~~~~~~~~~~~~~
doll.cpp: In function 'void sub1()':
doll.cpp:111:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for(i=0;i<to[k].size();i++)
      |                 ~^~~~~~~~~~~~~
doll.cpp:118:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  118 |     while(X.size()>s) X.pop_back();
      |           ~~~~~~~~^~
doll.cpp:119:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  119 |     while(Y.size()>s) Y.pop_back();
      |           ~~~~~~~~^~
doll.cpp: In function 'void sub2()':
doll.cpp:132:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for(i=0;i<G.sink.size();i++)
      |             ~^~~~~~~~~~~~~~
doll.cpp:138:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  138 |     while(X.size()>s) X.pop_back();
      |           ~~~~~~~~^~
doll.cpp:139:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  139 |     while(Y.size()>s) Y.pop_back();
      |           ~~~~~~~~^~
doll.cpp: In function 'void sub_same()':
doll.cpp:176:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  176 |     while(X.size()>s) X.pop_back();
      |           ~~~~~~~~^~
doll.cpp:177:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  177 |     while(Y.size()>s) Y.pop_back();
      |           ~~~~~~~~^~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29308 KB Output is correct
2 Correct 29 ms 34544 KB Output is correct
3 Correct 23 ms 34128 KB Output is correct
4 Correct 6 ms 29272 KB Output is correct
5 Correct 13 ms 30296 KB Output is correct
6 Correct 31 ms 36428 KB Output is correct
7 Correct 7 ms 29272 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29308 KB Output is correct
2 Correct 29 ms 34544 KB Output is correct
3 Correct 23 ms 34128 KB Output is correct
4 Correct 6 ms 29272 KB Output is correct
5 Correct 13 ms 30296 KB Output is correct
6 Correct 31 ms 36428 KB Output is correct
7 Correct 7 ms 29272 KB Output is correct
8 Correct 47 ms 39216 KB Output is correct
9 Correct 48 ms 39820 KB Output is correct
10 Correct 76 ms 43348 KB Output is correct
11 Correct 7 ms 31324 KB Output is correct
12 Correct 6 ms 31332 KB Output is correct
13 Correct 7 ms 31372 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29308 KB Output is correct
2 Correct 29 ms 34544 KB Output is correct
3 Correct 23 ms 34128 KB Output is correct
4 Correct 6 ms 29272 KB Output is correct
5 Correct 13 ms 30296 KB Output is correct
6 Correct 31 ms 36428 KB Output is correct
7 Correct 7 ms 29272 KB Output is correct
8 Correct 47 ms 39216 KB Output is correct
9 Correct 48 ms 39820 KB Output is correct
10 Correct 76 ms 43348 KB Output is correct
11 Correct 7 ms 31324 KB Output is correct
12 Correct 6 ms 31332 KB Output is correct
13 Correct 7 ms 31372 KB Output is correct
14 Correct 98 ms 46104 KB Output is correct
15 Correct 50 ms 40384 KB Output is correct
16 Correct 73 ms 44008 KB Output is correct
17 Correct 7 ms 33372 KB Output is correct
18 Correct 6 ms 33372 KB Output is correct
19 Correct 6 ms 33372 KB Output is correct
20 Correct 77 ms 45420 KB Output is correct
21 Correct 7 ms 33368 KB Output is correct
22 Correct 8 ms 33372 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31324 KB Output is correct
2 Correct 6 ms 31372 KB Output is correct
3 Correct 6 ms 31324 KB Output is correct
4 Correct 7 ms 31324 KB Output is correct
5 Correct 7 ms 33372 KB Output is correct
6 Correct 6 ms 31320 KB Output is correct
7 Correct 6 ms 31324 KB Output is correct
8 Correct 6 ms 31372 KB Output is correct

Subtask #5
9.4501648296 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 33372 KB Output is partially correct
2 Correct 35 ms 42964 KB Output is correct
3 Partially correct 59 ms 49152 KB Output is partially correct
4 Correct 69 ms 51956 KB Output is correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 33372 KB Output is partially correct
2 Correct 35 ms 42964 KB Output is correct
3 Partially correct 59 ms 49152 KB Output is partially correct
4 Correct 69 ms 51956 KB Output is correct
5 Partially correct 86 ms 53328 KB Output is partially correct
6 Partially correct 85 ms 52008 KB Output is partially correct
7 Partially correct 87 ms 53072 KB Output is partially correct
8 Partially correct 88 ms 51484 KB Output is partially correct
9 Partially correct 63 ms 49984 KB Output is partially correct
10 Partially correct 75 ms 52756 KB Output is partially correct
11 Partially correct 75 ms 52728 KB Output is partially correct
12 Partially correct 63 ms 49876 KB Output is partially correct
13 Correct 49 ms 42948 KB Output is correct
14 Partially correct 72 ms 50884 KB Output is partially correct
15 Partially correct 73 ms 50384 KB Output is partially correct
16 Partially correct 9 ms 31836 KB Output is partially correct
17 Correct 43 ms 42516 KB Output is correct
18 Correct 42 ms 43460 KB Output is correct
19 Partially correct 63 ms 50384 KB Output is partially correct
20 Partially correct 77 ms 50212 KB Output is partially correct
21 Partially correct 73 ms 50992 KB Output is partially correct
22 Partially correct 74 ms 50684 KB Output is partially correct