답안 #983657

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
983657	2024-05-15T21:08:31 Z	Zbyszek99	Two Transportations (JOI19_transportations)	C++17	100 / 100	1032 ms	60568 KB

Azer
Baijan

#include <bits/stdc++.h>
#include "Azer.h"
#define ff first 
#define ss second
using namespace std;



struct Compare {
    bool operator()(pair<int,int> a, pair<int,int> b) {
        return a > b; 
    }
};

int GETTING_VAL= 0;
int GETTING_V = 1;

int ans[2001];
int n,m;
vector<pair<int,int>> graf[2001];
priority_queue<pair<int,int>, vector<pair<int,int>>, Compare> pri;
int akt_odl;
int oper;
int how_many_bits;
int num;
int new_v;
int tryb;
void SendNum(int x, int wiel)
{
    for(int bit = 0; bit < wiel; bit++)
    {
        if(x & (1 << bit))
        {
            SendA(1);
        }
        else
        {
            SendA(0);
        }
    }
}



void InitA(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> C)
{
  // odw[0] = 1;
    ans[0] = 0;
    n = N;
    m = M;
    for(int i = 0; i < m; i++)
    {
        graf[U[i]].push_back({C[i],V[i]});
        graf[V[i]].push_back({C[i],U[i]});
    }
    for(auto& it: graf[0])
    {
        pri.push(it);
    }
    pri.push({1e9,2000});
    pair<int,int> t = pri.top();
    SendNum(min(t.ff - akt_odl,501),9);
}

void ReceiveA(bool x)
{
    if(tryb == GETTING_VAL)
    {
        if(x) num += (1 << how_many_bits);
        how_many_bits++;
        if(how_many_bits == 9)
        {
            
            oper++;
            if(oper == n) return;
            while((int)pri.size() != 0 && (ans[pri.top().ss] != 0 || pri.top().ss == 0)) pri.pop();
            if(pri.size() == 0) pri.push({1e9,2000});
            //cout << num << " val A\n";
            //cout << "ja: " << pri.top().ff - akt_odl  << ", B: " << num << " akt_odl:"<< akt_odl<<"\n";
            if((pri.top().ff - akt_odl <= num && pri.top().ff != 1e9) || num == 501)
            {
             //   cout << "Sending to B: " << pri.top().ss << " info about v\n";
                SendNum(pri.top().ss,11);
                akt_odl = pri.top().ff;
                ans[pri.top().ss] = akt_odl;
                for(auto& it: graf[pri.top().ss])
                {
                        pri.push({it.ff + akt_odl, it.ss});
                }
                how_many_bits = 0;
                num = 0;
                pri.pop();
                while((int)pri.size() != 0 && (ans[pri.top().ss] != 0 || pri.top().ss == 0)) pri.pop();
                if(pri.size() == 0) pri.push({1e9,2000});
              //  cout << "Sending to B: " << min(pri.top().ff - akt_odl,501) << " info about min\n";
                SendNum(min(pri.top().ff - akt_odl,501),9); //only for Azer
            }
            else
            {
                new_v = 0;
                how_many_bits = 0;
                tryb = GETTING_V;
            }
        }
    }
    else
    {
        if(x) new_v += (1 << how_many_bits);
        how_many_bits++;
        if(how_many_bits == 11)
        {
          //  cout << new_v << "new_v A\n";
            tryb = GETTING_VAL;
            ans[new_v] = akt_odl+num;
            akt_odl += num;
            //odw[new_v] = 1;
           // cout << akt_odl << " akt_odl A\n";
            for(auto& it: graf[new_v])
            {
                pri.push({it.ff + akt_odl, it.ss});
                
            }
            how_many_bits = 0;
            num = 0;
            while((int)pri.size() != 0 && (ans[pri.top().ss] != 0 || pri.top().ss == 0)) pri.pop();
            if(pri.size() == 0) pri.push({1e9,2000});
           // cout << "Sending to B: " << min(pri.top().ff - akt_odl,501) << " info about min\n";
            SendNum(min(pri.top().ff - akt_odl,501),9);
        }
    }
}

vector<int> Answer()
{
    vector<int> ans2;
    for(int i = 0; i < n; i++) ans2.push_back(ans[i]);
    return ans2;
}

#include <bits/stdc++.h>
#include "Baijan.h"
#define ff first 
#define ss second
using namespace std;

namespace {

struct Compare {
    bool operator()(pair<int,int> a, pair<int,int> b) {
        return a > b; 
    }
};

int GETTING_VAL= 0;
int GETTING_V = 1;

int ans[2001];
int n,m;
vector<pair<int,int>> graf[2001];
priority_queue<pair<int,int>, vector<pair<int,int>>, Compare> pri;
int akt_odl;
int oper;
int how_many_bits;
int num;
int new_v;
int tryb;
void SendNum(int x, int wiel)
{
    for(int bit = 0; bit < wiel; bit++)
    {
        if(x & (1 << bit))
        {
            SendB(1);
        }
        else
        {
            SendB(0);
        }
    }
}

}

void InitB(int N, int M, vector<int> U, vector<int> V, vector<int> cost)
{
    ans[0] = 0;
    n = N;
    m = M;
    for(int i = 0; i < m; i++)
    {
        graf[U[i]].push_back({cost[i],V[i]});
        graf[V[i]].push_back({cost[i],U[i]});
    }
    for(auto& it: graf[0])
    {
        pri.push(it);
    }
    pri.push({1e9,2000});
    pair<int,int> t = pri.top();
    SendNum(min(t.ff - akt_odl,501),9);
}

void ReceiveB(bool x)
{
    if(tryb == GETTING_VAL)
    {
        if(x) num += (1 << how_many_bits);
        how_many_bits++;
        if(how_many_bits == 9)
        {
           // cout << num << " val B\n";
            oper++;
            if(oper == n) return;
            while((int)pri.size() != 0 && (ans[pri.top().ss] != 0 || pri.top().ss == 0)) pri.pop();
            if(pri.size() == 0) pri.push({1e9,2000});
           // cout << "ja: " << pri.top().ff - akt_odl << ", A: " << num << " akt_odl:"<< akt_odl<<"\n";
            if((pri.top().ff - akt_odl < num && pri.top().ff != 1e9)|| num == 501)
            {
              //  cout << "Sending to A: " << pri.top().ss << " info about v\n";
                SendNum(pri.top().ss,11);
                akt_odl = pri.top().ff;
                ans[pri.top().ss] = akt_odl;
                for(auto& it: graf[pri.top().ss])
                {
                        pri.push({it.ff + akt_odl, it.ss});
                }
                how_many_bits = 0;
                num = 0;
                pri.pop();
                while((int)pri.size() != 0 && (ans[pri.top().ss] != 0 || pri.top().ss == 0)) pri.pop();
                if(pri.size() == 0) pri.push({1e9,2000});
                //cout << "Sending to A: " << min(pri.top().ff - akt_odl,501) << " info about min\n";
                SendNum(min(pri.top().ff - akt_odl,501),9); //only for Azer
            }
            else
            {
                new_v = 0;
                how_many_bits = 0;
                tryb = GETTING_V;
            }
        }
    }
    else
    {
        if(x) new_v += (1 << how_many_bits);
        how_many_bits++;
        if(how_many_bits == 11)
        {
            //cout << new_v << "new_v B\n";
            tryb = GETTING_VAL;
            ans[new_v] = akt_odl+num;
            akt_odl += num;
            for(auto& it: graf[new_v])
            {
                pri.push({it.ff + akt_odl, it.ss});
            //    cout << it.ss << " nowy B\n";
            }
            how_many_bits = 0;
            num = 0;
            while((int)pri.size() != 0 && (ans[pri.top().ss] != 0 || pri.top().ss == 0)) pri.pop();
            if(pri.size() == 0) pri.push({1e9,2000});
          //  cout << pri.top().ss << " nowy_max B\n";
           // cout << "Sending to A: " << min(pri.top().ff - akt_odl,501) << " info about min\n";
            SendNum(min(pri.top().ff - akt_odl,501),9);
        }
    }
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	421 ms	1076 KB	Output is correct
2	Correct	0 ms	664 KB	Output is correct
3	Correct	318 ms	1084 KB	Output is correct
4	Correct	456 ms	10260 KB	Output is correct
5	Correct	12 ms	2100 KB	Output is correct
6	Correct	362 ms	3436 KB	Output is correct

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	664 KB	Output is correct
2	Correct	420 ms	1124 KB	Output is correct
3	Correct	376 ms	1200 KB	Output is correct
4	Correct	698 ms	28040 KB	Output is correct
5	Correct	703 ms	29544 KB	Output is correct
6	Correct	61 ms	788 KB	Output is correct
7	Correct	659 ms	30876 KB	Output is correct

Subtask #3
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	333 ms	1388 KB	Output is correct
2	Correct	1 ms	664 KB	Output is correct
3	Correct	316 ms	1068 KB	Output is correct
4	Correct	410 ms	1148 KB	Output is correct
5	Correct	346 ms	1148 KB	Output is correct
6	Correct	317 ms	1092 KB	Output is correct
7	Correct	406 ms	1152 KB	Output is correct
8	Correct	364 ms	1060 KB	Output is correct
9	Correct	406 ms	1056 KB	Output is correct
10	Correct	418 ms	1084 KB	Output is correct

Subtask #4
38.0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	135 ms	816 KB	Output is correct
2	Correct	194 ms	792 KB	Output is correct
3	Correct	301 ms	13448 KB	Output is correct
4	Correct	144 ms	844 KB	Output is correct
5	Correct	210 ms	10364 KB	Output is correct
6	Correct	114 ms	844 KB	Output is correct
7	Correct	173 ms	664 KB	Output is correct
8	Correct	135 ms	1108 KB	Output is correct
9	Correct	375 ms	25428 KB	Output is correct
10	Correct	400 ms	24504 KB	Output is correct
11	Correct	599 ms	48600 KB	Output is correct
12	Correct	507 ms	46316 KB	Output is correct
13	Correct	163 ms	1088 KB	Output is correct
14	Correct	0 ms	916 KB	Output is correct

Subtask #5
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	135 ms	816 KB	Output is correct
2	Correct	194 ms	792 KB	Output is correct
3	Correct	301 ms	13448 KB	Output is correct
4	Correct	144 ms	844 KB	Output is correct
5	Correct	210 ms	10364 KB	Output is correct
6	Correct	114 ms	844 KB	Output is correct
7	Correct	173 ms	664 KB	Output is correct
8	Correct	135 ms	1108 KB	Output is correct
9	Correct	375 ms	25428 KB	Output is correct
10	Correct	400 ms	24504 KB	Output is correct
11	Correct	599 ms	48600 KB	Output is correct
12	Correct	507 ms	46316 KB	Output is correct
13	Correct	163 ms	1088 KB	Output is correct
14	Correct	0 ms	916 KB	Output is correct
15	Correct	247 ms	1020 KB	Output is correct
16	Correct	158 ms	1124 KB	Output is correct
17	Correct	170 ms	1124 KB	Output is correct
18	Correct	282 ms	10164 KB	Output is correct
19	Correct	155 ms	1128 KB	Output is correct
20	Correct	319 ms	10708 KB	Output is correct
21	Correct	166 ms	1140 KB	Output is correct
22	Correct	216 ms	888 KB	Output is correct
23	Correct	461 ms	27928 KB	Output is correct
24	Correct	428 ms	28604 KB	Output is correct
25	Correct	769 ms	56608 KB	Output is correct
26	Correct	635 ms	50712 KB	Output is correct
27	Correct	174 ms	1160 KB	Output is correct

Subtask #6
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	135 ms	816 KB	Output is correct
2	Correct	194 ms	792 KB	Output is correct
3	Correct	301 ms	13448 KB	Output is correct
4	Correct	144 ms	844 KB	Output is correct
5	Correct	210 ms	10364 KB	Output is correct
6	Correct	114 ms	844 KB	Output is correct
7	Correct	173 ms	664 KB	Output is correct
8	Correct	135 ms	1108 KB	Output is correct
9	Correct	375 ms	25428 KB	Output is correct
10	Correct	400 ms	24504 KB	Output is correct
11	Correct	599 ms	48600 KB	Output is correct
12	Correct	507 ms	46316 KB	Output is correct
13	Correct	163 ms	1088 KB	Output is correct
14	Correct	0 ms	916 KB	Output is correct
15	Correct	247 ms	1020 KB	Output is correct
16	Correct	158 ms	1124 KB	Output is correct
17	Correct	170 ms	1124 KB	Output is correct
18	Correct	282 ms	10164 KB	Output is correct
19	Correct	155 ms	1128 KB	Output is correct
20	Correct	319 ms	10708 KB	Output is correct
21	Correct	166 ms	1140 KB	Output is correct
22	Correct	216 ms	888 KB	Output is correct
23	Correct	461 ms	27928 KB	Output is correct
24	Correct	428 ms	28604 KB	Output is correct
25	Correct	769 ms	56608 KB	Output is correct
26	Correct	635 ms	50712 KB	Output is correct
27	Correct	174 ms	1160 KB	Output is correct
28	Correct	224 ms	1044 KB	Output is correct
29	Correct	304 ms	1032 KB	Output is correct
30	Correct	433 ms	24420 KB	Output is correct
31	Correct	171 ms	1276 KB	Output is correct
32	Correct	481 ms	21312 KB	Output is correct
33	Correct	225 ms	1104 KB	Output is correct
34	Correct	217 ms	1164 KB	Output is correct
35	Correct	263 ms	1168 KB	Output is correct
36	Correct	538 ms	31864 KB	Output is correct
37	Correct	552 ms	30176 KB	Output is correct
38	Correct	882 ms	60568 KB	Output is correct
39	Correct	708 ms	59028 KB	Output is correct
40	Correct	221 ms	1248 KB	Output is correct

Subtask #7
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	421 ms	1076 KB	Output is correct
2	Correct	0 ms	664 KB	Output is correct
3	Correct	318 ms	1084 KB	Output is correct
4	Correct	456 ms	10260 KB	Output is correct
5	Correct	12 ms	2100 KB	Output is correct
6	Correct	362 ms	3436 KB	Output is correct
7	Correct	0 ms	664 KB	Output is correct
8	Correct	420 ms	1124 KB	Output is correct
9	Correct	376 ms	1200 KB	Output is correct
10	Correct	698 ms	28040 KB	Output is correct
11	Correct	703 ms	29544 KB	Output is correct
12	Correct	61 ms	788 KB	Output is correct
13	Correct	659 ms	30876 KB	Output is correct
14	Correct	333 ms	1388 KB	Output is correct
15	Correct	1 ms	664 KB	Output is correct
16	Correct	316 ms	1068 KB	Output is correct
17	Correct	410 ms	1148 KB	Output is correct
18	Correct	346 ms	1148 KB	Output is correct
19	Correct	317 ms	1092 KB	Output is correct
20	Correct	406 ms	1152 KB	Output is correct
21	Correct	364 ms	1060 KB	Output is correct
22	Correct	406 ms	1056 KB	Output is correct
23	Correct	418 ms	1084 KB	Output is correct
24	Correct	135 ms	816 KB	Output is correct
25	Correct	194 ms	792 KB	Output is correct
26	Correct	301 ms	13448 KB	Output is correct
27	Correct	144 ms	844 KB	Output is correct
28	Correct	210 ms	10364 KB	Output is correct
29	Correct	114 ms	844 KB	Output is correct
30	Correct	173 ms	664 KB	Output is correct
31	Correct	135 ms	1108 KB	Output is correct
32	Correct	375 ms	25428 KB	Output is correct
33	Correct	400 ms	24504 KB	Output is correct
34	Correct	599 ms	48600 KB	Output is correct
35	Correct	507 ms	46316 KB	Output is correct
36	Correct	163 ms	1088 KB	Output is correct
37	Correct	0 ms	916 KB	Output is correct
38	Correct	247 ms	1020 KB	Output is correct
39	Correct	158 ms	1124 KB	Output is correct
40	Correct	170 ms	1124 KB	Output is correct
41	Correct	282 ms	10164 KB	Output is correct
42	Correct	155 ms	1128 KB	Output is correct
43	Correct	319 ms	10708 KB	Output is correct
44	Correct	166 ms	1140 KB	Output is correct
45	Correct	216 ms	888 KB	Output is correct
46	Correct	461 ms	27928 KB	Output is correct
47	Correct	428 ms	28604 KB	Output is correct
48	Correct	769 ms	56608 KB	Output is correct
49	Correct	635 ms	50712 KB	Output is correct
50	Correct	174 ms	1160 KB	Output is correct
51	Correct	224 ms	1044 KB	Output is correct
52	Correct	304 ms	1032 KB	Output is correct
53	Correct	433 ms	24420 KB	Output is correct
54	Correct	171 ms	1276 KB	Output is correct
55	Correct	481 ms	21312 KB	Output is correct
56	Correct	225 ms	1104 KB	Output is correct
57	Correct	217 ms	1164 KB	Output is correct
58	Correct	263 ms	1168 KB	Output is correct
59	Correct	538 ms	31864 KB	Output is correct
60	Correct	552 ms	30176 KB	Output is correct
61	Correct	882 ms	60568 KB	Output is correct
62	Correct	708 ms	59028 KB	Output is correct
63	Correct	221 ms	1248 KB	Output is correct
64	Correct	352 ms	1288 KB	Output is correct
65	Correct	544 ms	26528 KB	Output is correct
66	Correct	594 ms	23460 KB	Output is correct
67	Correct	325 ms	1460 KB	Output is correct
68	Correct	305 ms	1248 KB	Output is correct
69	Correct	1032 ms	59160 KB	Output is correct
70	Correct	923 ms	50760 KB	Output is correct
71	Correct	338 ms	7116 KB	Output is correct
72	Correct	347 ms	1792 KB	Output is correct

답안 #983657

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 8.0 / 8.0

Subtask #3 8.0 / 8.0

Subtask #4 38.0 / 38.0

Subtask #5 14.0 / 14.0

Subtask #6 10.0 / 10.0

Subtask #7 16.0 / 16.0

Subtask #1
6.0 / 6.0

Subtask #2
8.0 / 8.0

Subtask #3
8.0 / 8.0

Subtask #4
38.0 / 38.0

Subtask #5
14.0 / 14.0

Subtask #6
10.0 / 10.0

Subtask #7
16.0 / 16.0