oj.uz

Submission #931308

# Submission time Handle Problem Language Result Execution time Memory
931308 2024-02-21T15:04:12 Z HuyQuang_re_Zero Mechanical Doll (IOI18_doll) C++14
63 / 100
 88 ms 53448 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]]=numa[a.X[i]];
        res.Y[numa[i]]=numa[a.Y[i]];
    }
    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]]=numb[b.X[i]];
        res.Y[numb[i]]=numb[b.Y[i]];
    }
    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 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 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();
      |           ~~~~~~~~^~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29276 KB Output is correct
2 Correct 27 ms 34552 KB Output is correct
3 Correct 23 ms 34136 KB Output is correct
4 Correct 7 ms 29276 KB Output is correct
5 Correct 14 ms 30340 KB Output is correct
6 Correct 31 ms 36584 KB Output is correct
7 Correct 6 ms 29276 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29276 KB Output is correct
2 Correct 27 ms 34552 KB Output is correct
3 Correct 23 ms 34136 KB Output is correct
4 Correct 7 ms 29276 KB Output is correct
5 Correct 14 ms 30340 KB Output is correct
6 Correct 31 ms 36584 KB Output is correct
7 Correct 6 ms 29276 KB Output is correct
8 Correct 60 ms 39240 KB Output is correct
9 Correct 46 ms 39800 KB Output is correct
10 Correct 70 ms 43256 KB Output is correct
11 Correct 7 ms 31324 KB Output is correct
12 Correct 6 ms 31324 KB Output is correct
13 Correct 7 ms 31324 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29276 KB Output is correct
2 Correct 27 ms 34552 KB Output is correct
3 Correct 23 ms 34136 KB Output is correct
4 Correct 7 ms 29276 KB Output is correct
5 Correct 14 ms 30340 KB Output is correct
6 Correct 31 ms 36584 KB Output is correct
7 Correct 6 ms 29276 KB Output is correct
8 Correct 60 ms 39240 KB Output is correct
9 Correct 46 ms 39800 KB Output is correct
10 Correct 70 ms 43256 KB Output is correct
11 Correct 7 ms 31324 KB Output is correct
12 Correct 6 ms 31324 KB Output is correct
13 Correct 7 ms 31324 KB Output is correct
14 Correct 88 ms 46084 KB Output is correct
15 Correct 50 ms 40228 KB Output is correct
16 Correct 72 ms 44176 KB Output is correct
17 Correct 7 ms 33372 KB Output is correct
18 Correct 7 ms 33372 KB Output is correct
19 Correct 7 ms 33372 KB Output is correct
20 Correct 80 ms 45412 KB Output is correct
21 Correct 7 ms 33368 KB Output is correct
22 Correct 6 ms 33404 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31324 KB Output is correct
2 Correct 6 ms 31356 KB Output is correct
3 Correct 8 ms 31344 KB Output is correct
4 Correct 6 ms 31364 KB Output is correct
5 Correct 7 ms 31324 KB Output is correct
6 Correct 7 ms 31580 KB Output is correct
7 Correct 6 ms 31320 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 7 ms 31320 KB Output is partially correct
2 Correct 41 ms 42948 KB Output is correct
3 Partially correct 63 ms 50512 KB Output is partially correct
4 Partially correct 74 ms 52912 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 7 ms 31320 KB Output is partially correct
2 Correct 41 ms 42948 KB Output is correct
3 Partially correct 63 ms 50512 KB Output is partially correct
4 Partially correct 74 ms 52912 KB Output is partially correct
5 Partially correct 86 ms 52944 KB Output is partially correct
6 Partially correct 82 ms 51236 KB Output is partially correct
7 Partially correct 86 ms 52700 KB Output is partially correct
8 Partially correct 79 ms 52252 KB Output is partially correct
9 Partially correct 62 ms 50092 KB Output is partially correct
10 Partially correct 79 ms 53448 KB Output is partially correct
11 Partially correct 75 ms 52468 KB Output is partially correct
12 Partially correct 69 ms 49880 KB Output is partially correct
13 Correct 48 ms 42960 KB Output is correct
14 Partially correct 70 ms 49604 KB Output is partially correct
15 Partially correct 73 ms 51404 KB Output is partially correct
16 Partially correct 8 ms 31836 KB Output is partially correct
17 Correct 44 ms 42692 KB Output is correct
18 Correct 43 ms 43360 KB Output is correct
19 Partially correct 63 ms 50680 KB Output is partially correct
20 Partially correct 74 ms 50652 KB Output is partially correct
21 Partially correct 71 ms 51808 KB Output is partially correct
22 Partially correct 72 ms 51496 KB Output is partially correct