oj.uz

Submission #363959

# Submission time Handle Problem Language Result Execution time Memory
363959 2021-02-07T16:17:25 Z Fysty Mechanical Doll (IOI18_doll) C++17
100 / 100
 200 ms 14964 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define MottoHayaku ios::sync_with_stdio(0);cin.tie(0);
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define F first
#define S second
#define pb push_back
//#define int ll
const int MOD=1e9+7;
const ll INF=1e16;
const int N=100005;
const int maxN=1e6;
vector<int> ed[N];
ll t=0,x[maxN],y[maxN],out[maxN],c[N],root,rev[maxN];
void get_switch(int cnt,int l,int par,int k)
{
    int mid=k/2;
    if(k==2)
    {
        if(cnt==2)
        {
            out[l]=par;
            out[l+1]=par;
        }
        else
        {
            x[-par]=root;
            out[l+1]=par;
        }
        return;
    }
    if(cnt>mid)
    {
        t--;
        x[-par]=t;
        get_switch(cnt-mid,l,t,mid);
        t--;
        y[-par]=t;
        get_switch(mid,l+mid,t,mid);
    }
    else
    {
        x[-par]=root;
        t--;
        y[-par]=t;
        get_switch(cnt,l+mid,t,mid);
    }
}
void answer(vector<int> c,vector<int> x,vector<int> y);
void create_circuit(int M,vector<int> A)
{
    vector<int> c(M+1,-1),X,Y;
    A.pb(0);
    ll n=A.size();
    ll k=1,cnt=0;
    while(k<n) k<<=1,cnt++;
    t=root=-1;
    get_switch(A.size(),0,-1,k);
    ll cur=0;
    rep(i,k)
    {
        ll tmp=0,a=i;
        rep(j,cnt)
        {
            if(i&(1<<j)) tmp|=(1<<cnt-1-j);
        }
        if(out[tmp]!=0)
        {
            if(x[-out[tmp]]!=0) y[-out[tmp]]=A[cur];
            else x[-out[tmp]]=A[cur];
            cur++;
        }
    }
    rep(i,-t) X.pb(x[i+1]),Y.pb(y[i+1]);
    //rep(i,c.size()) cout<<i<<": "<<c[i]<<"\n";
    //rep(i,X.size()) cout<<-(i+1)<<": "<<X[i]<<" "<<Y[i]<<"\n";
    answer(c,X,Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:68:40: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   68 |             if(i&(1<<j)) tmp|=(1<<cnt-1-j);
      |                                   ~~~~~^~
doll.cpp:65:18: warning: unused variable 'a' [-Wunused-variable]
   65 |         ll tmp=0,a=i;
      |                  ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 64 ms 7644 KB Output is correct
3 Correct 45 ms 7520 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 14 ms 3788 KB Output is correct
6 Correct 59 ms 9756 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 64 ms 7644 KB Output is correct
3 Correct 45 ms 7520 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 14 ms 3788 KB Output is correct
6 Correct 59 ms 9756 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 81 ms 10716 KB Output is correct
9 Correct 83 ms 11104 KB Output is correct
10 Correct 114 ms 14964 KB Output is correct
11 Correct 3 ms 2636 KB Output is correct
12 Correct 3 ms 2676 KB Output is correct
13 Correct 3 ms 2636 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 64 ms 7644 KB Output is correct
3 Correct 45 ms 7520 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 14 ms 3788 KB Output is correct
6 Correct 59 ms 9756 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 81 ms 10716 KB Output is correct
9 Correct 83 ms 11104 KB Output is correct
10 Correct 114 ms 14964 KB Output is correct
11 Correct 3 ms 2636 KB Output is correct
12 Correct 3 ms 2676 KB Output is correct
13 Correct 3 ms 2636 KB Output is correct
14 Correct 115 ms 14644 KB Output is correct
15 Correct 77 ms 10324 KB Output is correct
16 Correct 113 ms 14460 KB Output is correct
17 Correct 2 ms 2636 KB Output is correct
18 Correct 2 ms 2636 KB Output is correct
19 Correct 3 ms 2636 KB Output is correct
20 Correct 121 ms 14824 KB Output is correct
21 Correct 2 ms 2636 KB Output is correct
22 Correct 3 ms 2636 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 3 ms 2636 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 78 ms 9836 KB Output is correct
3 Correct 84 ms 9864 KB Output is correct
4 Correct 111 ms 13524 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 78 ms 9836 KB Output is correct
3 Correct 84 ms 9864 KB Output is correct
4 Correct 111 ms 13524 KB Output is correct
5 Correct 119 ms 14428 KB Output is correct
6 Correct 159 ms 14208 KB Output is correct
7 Correct 103 ms 14204 KB Output is correct
8 Correct 200 ms 13932 KB Output is correct
9 Correct 84 ms 9780 KB Output is correct
10 Correct 104 ms 13856 KB Output is correct
11 Correct 169 ms 13524 KB Output is correct
12 Correct 72 ms 9776 KB Output is correct
13 Correct 75 ms 10168 KB Output is correct
14 Correct 74 ms 10148 KB Output is correct
15 Correct 82 ms 10340 KB Output is correct
16 Correct 6 ms 2892 KB Output is correct
17 Correct 70 ms 11088 KB Output is correct
18 Correct 75 ms 9836 KB Output is correct
19 Correct 95 ms 9860 KB Output is correct
20 Correct 115 ms 13760 KB Output is correct
21 Correct 115 ms 13524 KB Output is correct
22 Correct 110 ms 13528 KB Output is correct