oj.uz

답안 #829999

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
829999 2023-08-18T17:12:10 Z Antekb 저장 (Saveit) (IOI10_saveit) C++17
0 / 100
 1738 ms 12844 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, 10);
			}
		}
	}
	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, 10);
			}
		}
	}
	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(10);
				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 1737 ms 12844 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 105 call(s) of encode_bit()
3 Correct 773 ms 5712 KB Output is correct - 45290 call(s) of encode_bit()
4 Correct 1 ms 4608 KB Output is correct - 125 call(s) of encode_bit()
5 Incorrect 955 ms 6580 KB Output isn't correct
6 Incorrect 1147 ms 6772 KB Output isn't correct
7 Incorrect 1703 ms 7364 KB Output isn't correct
8 Correct 1551 ms 5408 KB Output is correct - 22777 call(s) of encode_bit()
9 Correct 786 ms 5468 KB Output is correct - 22850 call(s) of encode_bit()
10 Correct 795 ms 5476 KB Output is correct - 22610 call(s) of encode_bit()
11 Incorrect 843 ms 5984 KB Output isn't correct
12 Correct 998 ms 5528 KB Output is correct - 16990 call(s) of encode_bit()
13 Incorrect 1523 ms 6920 KB Output isn't correct
14 Correct 1012 ms 5436 KB Output is correct - 25910 call(s) of encode_bit()
15 Correct 1027 ms 5592 KB Output is correct - 27900 call(s) of encode_bit()
16 Correct 1154 ms 6668 KB Output is correct - 34110 call(s) of encode_bit()
17 Incorrect 1115 ms 6468 KB Output isn't correct
18 Correct 1259 ms 6952 KB Output is correct - 47690 call(s) of encode_bit()
19 Incorrect 1377 ms 6492 KB Output isn't correct
20 Incorrect 1174 ms 7592 KB Output isn't correct
21 Incorrect 1297 ms 7624 KB Output isn't correct
22 Incorrect 1738 ms 7056 KB Output isn't correct
23 Incorrect 1373 ms 8120 KB Output isn't correct

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1737 ms 12844 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 105 call(s) of encode_bit()
3 Correct 773 ms 5712 KB Output is correct - 45290 call(s) of encode_bit()
4 Correct 1 ms 4608 KB Output is correct - 125 call(s) of encode_bit()
5 Incorrect 955 ms 6580 KB Output isn't correct
6 Incorrect 1147 ms 6772 KB Output isn't correct
7 Incorrect 1703 ms 7364 KB Output isn't correct
8 Correct 1551 ms 5408 KB Output is correct - 22777 call(s) of encode_bit()
9 Correct 786 ms 5468 KB Output is correct - 22850 call(s) of encode_bit()
10 Correct 795 ms 5476 KB Output is correct - 22610 call(s) of encode_bit()
11 Incorrect 843 ms 5984 KB Output isn't correct
12 Correct 998 ms 5528 KB Output is correct - 16990 call(s) of encode_bit()
13 Incorrect 1523 ms 6920 KB Output isn't correct
14 Correct 1012 ms 5436 KB Output is correct - 25910 call(s) of encode_bit()
15 Correct 1027 ms 5592 KB Output is correct - 27900 call(s) of encode_bit()
16 Correct 1154 ms 6668 KB Output is correct - 34110 call(s) of encode_bit()
17 Incorrect 1115 ms 6468 KB Output isn't correct
18 Correct 1259 ms 6952 KB Output is correct - 47690 call(s) of encode_bit()
19 Incorrect 1377 ms 6492 KB Output isn't correct
20 Incorrect 1174 ms 7592 KB Output isn't correct
21 Incorrect 1297 ms 7624 KB Output isn't correct
22 Incorrect 1738 ms 7056 KB Output isn't correct
23 Incorrect 1373 ms 8120 KB Output isn't correct

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1737 ms 12844 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 105 call(s) of encode_bit()
3 Correct 773 ms 5712 KB Output is correct - 45290 call(s) of encode_bit()
4 Correct 1 ms 4608 KB Output is correct - 125 call(s) of encode_bit()
5 Incorrect 955 ms 6580 KB Output isn't correct
6 Incorrect 1147 ms 6772 KB Output isn't correct
7 Incorrect 1703 ms 7364 KB Output isn't correct
8 Correct 1551 ms 5408 KB Output is correct - 22777 call(s) of encode_bit()
9 Correct 786 ms 5468 KB Output is correct - 22850 call(s) of encode_bit()
10 Correct 795 ms 5476 KB Output is correct - 22610 call(s) of encode_bit()
11 Incorrect 843 ms 5984 KB Output isn't correct
12 Correct 998 ms 5528 KB Output is correct - 16990 call(s) of encode_bit()
13 Incorrect 1523 ms 6920 KB Output isn't correct
14 Correct 1012 ms 5436 KB Output is correct - 25910 call(s) of encode_bit()
15 Correct 1027 ms 5592 KB Output is correct - 27900 call(s) of encode_bit()
16 Correct 1154 ms 6668 KB Output is correct - 34110 call(s) of encode_bit()
17 Incorrect 1115 ms 6468 KB Output isn't correct
18 Correct 1259 ms 6952 KB Output is correct - 47690 call(s) of encode_bit()
19 Incorrect 1377 ms 6492 KB Output isn't correct
20 Incorrect 1174 ms 7592 KB Output isn't correct
21 Incorrect 1297 ms 7624 KB Output isn't correct
22 Incorrect 1738 ms 7056 KB Output isn't correct
23 Incorrect 1373 ms 8120 KB Output isn't correct

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1737 ms 12844 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 105 call(s) of encode_bit()
3 Correct 773 ms 5712 KB Output is correct - 45290 call(s) of encode_bit()
4 Correct 1 ms 4608 KB Output is correct - 125 call(s) of encode_bit()
5 Incorrect 955 ms 6580 KB Output isn't correct
6 Incorrect 1147 ms 6772 KB Output isn't correct
7 Incorrect 1703 ms 7364 KB Output isn't correct
8 Correct 1551 ms 5408 KB Output is correct - 22777 call(s) of encode_bit()
9 Correct 786 ms 5468 KB Output is correct - 22850 call(s) of encode_bit()
10 Correct 795 ms 5476 KB Output is correct - 22610 call(s) of encode_bit()
11 Incorrect 843 ms 5984 KB Output isn't correct
12 Correct 998 ms 5528 KB Output is correct - 16990 call(s) of encode_bit()
13 Incorrect 1523 ms 6920 KB Output isn't correct
14 Correct 1012 ms 5436 KB Output is correct - 25910 call(s) of encode_bit()
15 Correct 1027 ms 5592 KB Output is correct - 27900 call(s) of encode_bit()
16 Correct 1154 ms 6668 KB Output is correct - 34110 call(s) of encode_bit()
17 Incorrect 1115 ms 6468 KB Output isn't correct
18 Correct 1259 ms 6952 KB Output is correct - 47690 call(s) of encode_bit()
19 Incorrect 1377 ms 6492 KB Output isn't correct
20 Incorrect 1174 ms 7592 KB Output isn't correct
21 Incorrect 1297 ms 7624 KB Output isn't correct
22 Incorrect 1738 ms 7056 KB Output isn't correct
23 Incorrect 1373 ms 8120 KB Output isn't correct