oj.uz

Submission #565146

# Submission time Handle Problem Language Result Execution time Memory
565146 2022-05-20T10:55:56 Z MrDeboo Saveit (IOI10_saveit) C++17
25 / 100
 358 ms 18960 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
void encode(int n, int h, int p, int v1[], int v2[]){
    srand(time(NULL));
    vector<int>vct[n];
    for(int i=0;i<p;i++){
        vct[v1[i]].push_back(v2[i]);
        vct[v2[i]].push_back(v1[i]);
    }
    priority_queue<pair<int,pair<int,int>>>pq;
    map<pair<int,int>,bool>mp;
    for(int i=0;i<h;i++){
        deque<pair<int,int>>dq={{0,i}};
        vector<bool>vis(n);
        while(dq.size()){
            pair<int,int>p=dq.front();
            dq.pop_front();
            for(auto &w:vct[p.second]){
                if(vis[w])continue;
                vis[w]=1;
                if(!mp[{min(w,p.second),max(w,p.second)}]){
                    pq.push({rand(),{min(w,p.second),max(w,p.second)}});
                    mp[{min(w,p.second),max(w,p.second)}]=1;
                }
                dq.push_back({p.first+1,w});
            }
        }
    }
    int tot=1000000/20;
    while(tot--){
        pair<int,int>pr;
        if(pq.empty())pr={0,0};
        else{
            pr=pq.top().second;
            pq.pop();
        }
        for(int i=0;i<10;i++)encode_bit((!!(pr.first&(1<<i))));
        for(int i=0;i<10;i++)encode_bit((!!(pr.second&(1<<i))));
    }
}

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
void decode(int n, int h) {
    vector<int>vct[n];
    for(int i=0;i<1000000/20;i++){
        int a=0,b=0;
        for(int w=0;w<10;w++)a+=(1<<w)*decode_bit();
        for(int w=0;w<10;w++)b+=(1<<w)*decode_bit();
        vct[a].push_back(b);
        vct[b].push_back(a);
    }
    for(int i=0;i<h;i++){
        deque<pair<int,int>>dq={{0,i}};
        vector<bool>vis(n);
        vis[i]=1;
        while(dq.size()){
            pair<int,int>p=dq.front();
            dq.pop_front();
            hops(i,p.second,p.first);
            for(auto &w:vct[p.second]){if(!vis[w]){dq.push_back({p.first+1,w});vis[w]=1;}}
        }
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 18960 KB Output is partially correct - 1000000 call(s) of encode_bit()
2 Correct 142 ms 13088 KB Output is partially correct - 1000000 call(s) of encode_bit()
3 Correct 184 ms 13608 KB Output is partially correct - 1000000 call(s) of encode_bit()
4 Correct 162 ms 13072 KB Output is partially correct - 1000000 call(s) of encode_bit()
5 Correct 169 ms 14192 KB Output is partially correct - 1000000 call(s) of encode_bit()
6 Correct 188 ms 14224 KB Output is partially correct - 1000000 call(s) of encode_bit()
7 Correct 196 ms 15052 KB Output is partially correct - 1000000 call(s) of encode_bit()
8 Correct 162 ms 13396 KB Output is partially correct - 1000000 call(s) of encode_bit()
9 Correct 194 ms 13632 KB Output is partially correct - 1000000 call(s) of encode_bit()
10 Correct 166 ms 13392 KB Output is partially correct - 1000000 call(s) of encode_bit()
11 Correct 167 ms 13756 KB Output is partially correct - 1000000 call(s) of encode_bit()
12 Correct 177 ms 13384 KB Output is partially correct - 1000000 call(s) of encode_bit()
13 Correct 242 ms 14860 KB Output is partially correct - 1000000 call(s) of encode_bit()
14 Correct 204 ms 13408 KB Output is partially correct - 1000000 call(s) of encode_bit()
15 Correct 198 ms 13584 KB Output is partially correct - 1000000 call(s) of encode_bit()
16 Correct 189 ms 14296 KB Output is partially correct - 1000000 call(s) of encode_bit()
17 Correct 238 ms 14164 KB Output is partially correct - 1000000 call(s) of encode_bit()
18 Correct 191 ms 14796 KB Output is partially correct - 1000000 call(s) of encode_bit()
19 Correct 219 ms 14356 KB Output is partially correct - 1000000 call(s) of encode_bit()
20 Correct 215 ms 15248 KB Output is partially correct - 1000000 call(s) of encode_bit()
21 Correct 221 ms 15308 KB Output is partially correct - 1000000 call(s) of encode_bit()
22 Correct 204 ms 15384 KB Output is partially correct - 1000000 call(s) of encode_bit()
23 Correct 214 ms 15936 KB Output is partially correct - 1000000 call(s) of encode_bit()

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 18960 KB Output is partially correct - 1000000 call(s) of encode_bit()
2 Correct 142 ms 13088 KB Output is partially correct - 1000000 call(s) of encode_bit()
3 Correct 184 ms 13608 KB Output is partially correct - 1000000 call(s) of encode_bit()
4 Correct 162 ms 13072 KB Output is partially correct - 1000000 call(s) of encode_bit()
5 Correct 169 ms 14192 KB Output is partially correct - 1000000 call(s) of encode_bit()
6 Correct 188 ms 14224 KB Output is partially correct - 1000000 call(s) of encode_bit()
7 Correct 196 ms 15052 KB Output is partially correct - 1000000 call(s) of encode_bit()
8 Correct 162 ms 13396 KB Output is partially correct - 1000000 call(s) of encode_bit()
9 Correct 194 ms 13632 KB Output is partially correct - 1000000 call(s) of encode_bit()
10 Correct 166 ms 13392 KB Output is partially correct - 1000000 call(s) of encode_bit()
11 Correct 167 ms 13756 KB Output is partially correct - 1000000 call(s) of encode_bit()
12 Correct 177 ms 13384 KB Output is partially correct - 1000000 call(s) of encode_bit()
13 Correct 242 ms 14860 KB Output is partially correct - 1000000 call(s) of encode_bit()
14 Correct 204 ms 13408 KB Output is partially correct - 1000000 call(s) of encode_bit()
15 Correct 198 ms 13584 KB Output is partially correct - 1000000 call(s) of encode_bit()
16 Correct 189 ms 14296 KB Output is partially correct - 1000000 call(s) of encode_bit()
17 Correct 238 ms 14164 KB Output is partially correct - 1000000 call(s) of encode_bit()
18 Correct 191 ms 14796 KB Output is partially correct - 1000000 call(s) of encode_bit()
19 Correct 219 ms 14356 KB Output is partially correct - 1000000 call(s) of encode_bit()
20 Correct 215 ms 15248 KB Output is partially correct - 1000000 call(s) of encode_bit()
21 Correct 221 ms 15308 KB Output is partially correct - 1000000 call(s) of encode_bit()
22 Correct 204 ms 15384 KB Output is partially correct - 1000000 call(s) of encode_bit()
23 Correct 214 ms 15936 KB Output is partially correct - 1000000 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 18960 KB Output is partially correct - 1000000 call(s) of encode_bit()
2 Correct 142 ms 13088 KB Output is partially correct - 1000000 call(s) of encode_bit()
3 Correct 184 ms 13608 KB Output is partially correct - 1000000 call(s) of encode_bit()
4 Correct 162 ms 13072 KB Output is partially correct - 1000000 call(s) of encode_bit()
5 Correct 169 ms 14192 KB Output is partially correct - 1000000 call(s) of encode_bit()
6 Correct 188 ms 14224 KB Output is partially correct - 1000000 call(s) of encode_bit()
7 Correct 196 ms 15052 KB Output is partially correct - 1000000 call(s) of encode_bit()
8 Correct 162 ms 13396 KB Output is partially correct - 1000000 call(s) of encode_bit()
9 Correct 194 ms 13632 KB Output is partially correct - 1000000 call(s) of encode_bit()
10 Correct 166 ms 13392 KB Output is partially correct - 1000000 call(s) of encode_bit()
11 Correct 167 ms 13756 KB Output is partially correct - 1000000 call(s) of encode_bit()
12 Correct 177 ms 13384 KB Output is partially correct - 1000000 call(s) of encode_bit()
13 Correct 242 ms 14860 KB Output is partially correct - 1000000 call(s) of encode_bit()
14 Correct 204 ms 13408 KB Output is partially correct - 1000000 call(s) of encode_bit()
15 Correct 198 ms 13584 KB Output is partially correct - 1000000 call(s) of encode_bit()
16 Correct 189 ms 14296 KB Output is partially correct - 1000000 call(s) of encode_bit()
17 Correct 238 ms 14164 KB Output is partially correct - 1000000 call(s) of encode_bit()
18 Correct 191 ms 14796 KB Output is partially correct - 1000000 call(s) of encode_bit()
19 Correct 219 ms 14356 KB Output is partially correct - 1000000 call(s) of encode_bit()
20 Correct 215 ms 15248 KB Output is partially correct - 1000000 call(s) of encode_bit()
21 Correct 221 ms 15308 KB Output is partially correct - 1000000 call(s) of encode_bit()
22 Correct 204 ms 15384 KB Output is partially correct - 1000000 call(s) of encode_bit()
23 Correct 214 ms 15936 KB Output is partially correct - 1000000 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 18960 KB Output is partially correct - 1000000 call(s) of encode_bit()
2 Correct 142 ms 13088 KB Output is partially correct - 1000000 call(s) of encode_bit()
3 Correct 184 ms 13608 KB Output is partially correct - 1000000 call(s) of encode_bit()
4 Correct 162 ms 13072 KB Output is partially correct - 1000000 call(s) of encode_bit()
5 Correct 169 ms 14192 KB Output is partially correct - 1000000 call(s) of encode_bit()
6 Correct 188 ms 14224 KB Output is partially correct - 1000000 call(s) of encode_bit()
7 Correct 196 ms 15052 KB Output is partially correct - 1000000 call(s) of encode_bit()
8 Correct 162 ms 13396 KB Output is partially correct - 1000000 call(s) of encode_bit()
9 Correct 194 ms 13632 KB Output is partially correct - 1000000 call(s) of encode_bit()
10 Correct 166 ms 13392 KB Output is partially correct - 1000000 call(s) of encode_bit()
11 Correct 167 ms 13756 KB Output is partially correct - 1000000 call(s) of encode_bit()
12 Correct 177 ms 13384 KB Output is partially correct - 1000000 call(s) of encode_bit()
13 Correct 242 ms 14860 KB Output is partially correct - 1000000 call(s) of encode_bit()
14 Correct 204 ms 13408 KB Output is partially correct - 1000000 call(s) of encode_bit()
15 Correct 198 ms 13584 KB Output is partially correct - 1000000 call(s) of encode_bit()
16 Correct 189 ms 14296 KB Output is partially correct - 1000000 call(s) of encode_bit()
17 Correct 238 ms 14164 KB Output is partially correct - 1000000 call(s) of encode_bit()
18 Correct 191 ms 14796 KB Output is partially correct - 1000000 call(s) of encode_bit()
19 Correct 219 ms 14356 KB Output is partially correct - 1000000 call(s) of encode_bit()
20 Correct 215 ms 15248 KB Output is partially correct - 1000000 call(s) of encode_bit()
21 Correct 221 ms 15308 KB Output is partially correct - 1000000 call(s) of encode_bit()
22 Correct 204 ms 15384 KB Output is partially correct - 1000000 call(s) of encode_bit()
23 Correct 214 ms 15936 KB Output is partially correct - 1000000 call(s) of encode_bit()