oj.uz

답안 #829536

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
829536 2023-08-18T12:20:10 Z Antekb 저장 (Saveit) (IOI10_saveit) C++17
0 / 100
 5422 ms 13768 KB 
#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define pp pop_back;
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
void nadaj(vi &V, int x, int b){
	for(int i=0; i<b; i++){
		V.pb(!!(x&(1<<i)));
	}
}
void encode2(vi &ans, int n, int h, int m, int *v1, int *v2){
	vi E[n];
	int czy[n][h], dist[n][h];
	for(int i=0; i<n; i++){
		for(int j=0; j<h; j++){
			czy[i][j]=(i==j);
			dist[i][j]=1e9*(i!=j);
		}
	}
	vi edg;
	for(int i=0; i<m; i++){
		E[v1[i]].pb(edg.size());
		edg.pb(v2[i]);
		E[v2[i]].pb(edg.size());
		edg.pb(v1[i]);
	}
	for(int s=0; s<h; s++){
		vi V;
		V.pb(s);
		for(int i=0; i<V.size(); i++){
			int v=V[i];
			for(int e:E[v]){
				if(dist[edg[e]][s]==1e9){
					dist[edg[e]][s]=dist[v][s]+1;
					V.pb(edg[e]);
				}
			}
		}
	}
	vi E2[n];
	for(int v=0; v<n; v++){
		int ile=0;
		for(int u=0; u<n; u++){
			if(u==v)continue;
			bool b=1;
			for(int i=0; i<h; i++){
				if(dist[u][i]+1<dist[v][i] || dist[v][i]+1<dist[u][i]){
					b=0;
				}
			}
			if(!b)continue;
			b=0;
			for(int i=0; i<h; i++){
				if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
					b=1;
				}
				if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
					b=1;
				}
			}
			if(b)ile++;
		}
		if(ile>=100){
			for(int u=0; u<n; u++){
				if(u==v)continue;
				bool b=1;
				for(int i=0; i<h; i++){
					if(dist[u][i]+1<dist[v][i] || dist[v][i]+1<dist[u][i]){
						b=0;
					}
				}
				if(!b)continue;
				for(int i=0; i<h; i++){
					if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
						czy[u][i]=1;
						E2[v].pb(u);
					}
					if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
						czy[v][i]=1;
						E2[v].pb(u);
					}
				}
			}
		}
	}
	int sum=0;
	for(int t=h; t>0; t--){
		for(int u=0; u<n; u++){
			for(int v=0; v<u; v++){
			bool b=1;
			for(int i=0; i<h; i++){
				if(dist[u][i]+1<dist[v][i] || dist[v][i]+1<dist[u][i]){
					b=0;
				}
			}
			if(!b)continue;
			int ile=0;
			for(int i=0; i<h; i++){
				if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
					ile++;
				}
				if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
					ile++;
				}
			}
			if(ile==t){
				//cerr<<t<<"\n";
				sum+=t;
				if(2*(u-v)<n)E2[v].pb(u-v);
				else E2[u].pb(v-u+n);
				for(int i=0; i<h; i++){
					if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
						czy[u][i]=1;
					}
					if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
						czy[v][i]=1;
					}
				}
			}
			}
		}
	}
	cerr<<sum<<"\n";
	for(int i=0; i<n; i++){
		sort(E2[i].begin(), E2[i].end());
		nadaj(ans, min((int)E2[i].size(), 100), 7);
		if(E2[i].size()>=100){
			vi V(n);
			for(int u:E2[i]){
				V[u]=1;
			}
			for(int j:V){
				nadaj(ans, j, 1);
			}
		}
		else{
			for(int u:E2[i]){
				nadaj(ans, u, 9);
			}
		}
	}
	return;
}
void encode3(vi &ans, int n, int h, int m, int *v1, int *v2){
	vi E[n];
	int czy[n][h], dist[n][h];
	for(int i=0; i<n; i++){
		for(int j=0; j<h; j++){
			czy[i][j]=(i==j);
			dist[i][j]=1e9*(i!=j);
		}
	}
	vi edg;
	for(int i=0; i<m; i++){
		E[v1[i]].pb(edg.size());
		edg.pb(v2[i]);
		E[v2[i]].pb(edg.size());
		edg.pb(v1[i]);
	}
	for(int s=0; s<h; s++){
		vi V;
		V.pb(s);
		for(int i=0; i<V.size(); i++){
			int v=V[i];
			for(int e:E[v]){
				if(dist[edg[e]][s]==1e9){
					dist[edg[e]][s]=dist[v][s]+1;
					V.pb(edg[e]);
				}
			}
		}
	}
	vi E2[n];
	int sum=0;
	for(int t=h; t>0; t--){
		for(int u=0; u<n; u++){
			for(int v=0; v<u; v++){
			bool b=1;
			for(int i=0; i<h; i++){
				if(dist[u][i]+1<dist[v][i] || dist[v][i]+1<dist[u][i]){
					b=0;
				}
			}
			if(!b)continue;
			int ile=0;
			for(int i=0; i<h; i++){
				if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
					ile++;
				}
				if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
					ile++;
				}
			}
			if(ile==t){
				//cerr<<t<<"\n";
				sum+=t;
				if(2*(u-v)<n)E2[v].pb(u-v);
				else E2[u].pb(v-u+n);
				for(int i=0; i<h; i++){
					if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
						czy[u][i]=1;
					}
					if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
						czy[v][i]=1;
					}
				}
			}
			}
		}
	}
	cerr<<sum<<"\n";
	for(int i=0; i<n; i++){
		sort(E2[i].begin(), E2[i].end());
		nadaj(ans, min((int)E2[i].size(), 100), 7);
		if(E2[i].size()>=100){
			vi V(n);
			for(int u:E2[i]){
				V[u]=1;
			}
			for(int j:V){
				nadaj(ans, j, 1);
			}
		}
		else{
			for(int u:E2[i]){
				nadaj(ans, u, 9);
			}
		}
	}
	return;
}
void encode(int n, int h, int m, int *v1, int *v2){
	vi V, V2;
	encode2(V, n, h, m, v1, v2);
	encode3(V2, n, h, m, v1, v2);
	if(V2.size()<V.size())V=V2;
	for(int i:V){
		encode_bit(i);
	}
}
#include "grader.h"
#include "decoder.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define pp pop_back;
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
int czytaj(int b){
	int x=0;
	for(int i=0; i<b; i++){
		x+=(int(decode_bit())<<i);
	}
	return x;
}
void decode(int n, int h) {
	vi E[n];
	for(int i=0;i<n; i++){
		int k=czytaj(7);
		//cerr<<k<<"\n";
		if(k==100){
			for(int j=0; j<n; j++){
				if(czytaj(1)){
					E[i].pb(j);
					E[j].pb(i);
				}
			}
		}
		else{
			while(k--){
				int j=czytaj(9);
				E[i].pb((i+j)%n);
				E[(j+i)%n].pb(i);
			}
		}
	}
	for(int s=0; s<h; s++){
		vi V;
		V.pb(s);
		vi dist(n, 1e9);
		dist[s]=0;
		for(int i=0; i<V.size(); i++){
			int v=V[i];
			for(int u:E[v]){
				if(dist[u]==1e9){
					dist[u]=dist[v]+1;
					V.pb(u);
				}
			}
		}
		for(int i=0; i<n; i++){
			hops(s, i, dist[i]);
		}
	}
}

Compilation message

encoder.cpp: In function 'void encode2(vi&, int, int, int, int*, int*)':
encoder.cpp:35:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int i=0; i<V.size(); i++){
      |                ~^~~~~~~~~
encoder.cpp: In function 'void encode3(vi&, int, int, int, int*, int*)':
encoder.cpp:168:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |   for(int i=0; i<V.size(); i++){
      |                ~^~~~~~~~~

decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:44:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(int i=0; i<V.size(); i++){
      |                ~^~~~~~~~~

Subtask #1
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5422 ms 13768 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 1 ms 4604 KB Output is correct - 98 call(s) of encode_bit()
3 Correct 1497 ms 6020 KB Output is correct - 39510 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 116 call(s) of encode_bit()
5 Correct 2287 ms 6796 KB Output is correct - 66717 call(s) of encode_bit()
6 Correct 2731 ms 6912 KB Output is correct - 69064 call(s) of encode_bit()
7 Incorrect 3429 ms 7520 KB Output isn't correct
8 Correct 2970 ms 5644 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 1547 ms 5560 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 1525 ms 5572 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 1646 ms 6184 KB Output is correct - 35530 call(s) of encode_bit()
12 Correct 1889 ms 5412 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 3023 ms 7392 KB Output isn't correct
14 Correct 1953 ms 5640 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1894 ms 5704 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 2284 ms 6952 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 2316 ms 6784 KB Output isn't correct
18 Correct 2889 ms 7448 KB Output is correct - 46921 call(s) of encode_bit()
19 Incorrect 2546 ms 6740 KB Output isn't correct
20 Incorrect 2824 ms 7776 KB Output isn't correct
21 Incorrect 3145 ms 8340 KB Output isn't correct
22 Incorrect 3313 ms 7924 KB Output isn't correct
23 Incorrect 3328 ms 9064 KB Output isn't correct

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5422 ms 13768 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 1 ms 4604 KB Output is correct - 98 call(s) of encode_bit()
3 Correct 1497 ms 6020 KB Output is correct - 39510 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 116 call(s) of encode_bit()
5 Correct 2287 ms 6796 KB Output is correct - 66717 call(s) of encode_bit()
6 Correct 2731 ms 6912 KB Output is correct - 69064 call(s) of encode_bit()
7 Incorrect 3429 ms 7520 KB Output isn't correct
8 Correct 2970 ms 5644 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 1547 ms 5560 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 1525 ms 5572 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 1646 ms 6184 KB Output is correct - 35530 call(s) of encode_bit()
12 Correct 1889 ms 5412 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 3023 ms 7392 KB Output isn't correct
14 Correct 1953 ms 5640 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1894 ms 5704 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 2284 ms 6952 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 2316 ms 6784 KB Output isn't correct
18 Correct 2889 ms 7448 KB Output is correct - 46921 call(s) of encode_bit()
19 Incorrect 2546 ms 6740 KB Output isn't correct
20 Incorrect 2824 ms 7776 KB Output isn't correct
21 Incorrect 3145 ms 8340 KB Output isn't correct
22 Incorrect 3313 ms 7924 KB Output isn't correct
23 Incorrect 3328 ms 9064 KB Output isn't correct

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5422 ms 13768 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 1 ms 4604 KB Output is correct - 98 call(s) of encode_bit()
3 Correct 1497 ms 6020 KB Output is correct - 39510 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 116 call(s) of encode_bit()
5 Correct 2287 ms 6796 KB Output is correct - 66717 call(s) of encode_bit()
6 Correct 2731 ms 6912 KB Output is correct - 69064 call(s) of encode_bit()
7 Incorrect 3429 ms 7520 KB Output isn't correct
8 Correct 2970 ms 5644 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 1547 ms 5560 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 1525 ms 5572 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 1646 ms 6184 KB Output is correct - 35530 call(s) of encode_bit()
12 Correct 1889 ms 5412 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 3023 ms 7392 KB Output isn't correct
14 Correct 1953 ms 5640 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1894 ms 5704 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 2284 ms 6952 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 2316 ms 6784 KB Output isn't correct
18 Correct 2889 ms 7448 KB Output is correct - 46921 call(s) of encode_bit()
19 Incorrect 2546 ms 6740 KB Output isn't correct
20 Incorrect 2824 ms 7776 KB Output isn't correct
21 Incorrect 3145 ms 8340 KB Output isn't correct
22 Incorrect 3313 ms 7924 KB Output isn't correct
23 Incorrect 3328 ms 9064 KB Output isn't correct

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5422 ms 13768 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 1 ms 4604 KB Output is correct - 98 call(s) of encode_bit()
3 Correct 1497 ms 6020 KB Output is correct - 39510 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 116 call(s) of encode_bit()
5 Correct 2287 ms 6796 KB Output is correct - 66717 call(s) of encode_bit()
6 Correct 2731 ms 6912 KB Output is correct - 69064 call(s) of encode_bit()
7 Incorrect 3429 ms 7520 KB Output isn't correct
8 Correct 2970 ms 5644 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 1547 ms 5560 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 1525 ms 5572 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 1646 ms 6184 KB Output is correct - 35530 call(s) of encode_bit()
12 Correct 1889 ms 5412 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 3023 ms 7392 KB Output isn't correct
14 Correct 1953 ms 5640 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1894 ms 5704 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 2284 ms 6952 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 2316 ms 6784 KB Output isn't correct
18 Correct 2889 ms 7448 KB Output is correct - 46921 call(s) of encode_bit()
19 Incorrect 2546 ms 6740 KB Output isn't correct
20 Incorrect 2824 ms 7776 KB Output isn't correct
21 Incorrect 3145 ms 8340 KB Output isn't correct
22 Incorrect 3313 ms 7924 KB Output isn't correct
23 Incorrect 3328 ms 9064 KB Output isn't correct