oj.uz

답안 #830001

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
830001 2023-08-18T17:16:28 Z Antekb 저장 (Saveit) (IOI10_saveit) C++17
0 / 100
 1841 ms 12764 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);
				else E2[u].pb(v);
				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-i+n)%n, 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, 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(9);
				E[i].pb((j+i)%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 1756 ms 12764 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 810 ms 5696 KB Output is correct - 41661 call(s) of encode_bit()
4 Correct 1 ms 4604 KB Output is correct - 116 call(s) of encode_bit()
5 Incorrect 1011 ms 6584 KB Output isn't correct
6 Incorrect 1170 ms 6776 KB Output isn't correct
7 Incorrect 1815 ms 7368 KB Output isn't correct
8 Correct 1186 ms 5452 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 797 ms 5476 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 823 ms 5484 KB Output is correct - 21049 call(s) of encode_bit()
11 Incorrect 872 ms 5980 KB Output isn't correct
12 Correct 938 ms 5272 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 1607 ms 6920 KB Output isn't correct
14 Correct 930 ms 5472 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 964 ms 5548 KB Output is correct - 26210 call(s) of encode_bit()
16 Correct 1037 ms 6624 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 1070 ms 6464 KB Output isn't correct
18 Correct 1190 ms 6920 KB Output is correct - 46921 call(s) of encode_bit()
19 Incorrect 1326 ms 6536 KB Output isn't correct
20 Incorrect 1216 ms 7424 KB Output isn't correct
21 Incorrect 1339 ms 7812 KB Output isn't correct
22 Incorrect 1841 ms 7052 KB Output isn't correct
23 Incorrect 1420 ms 7948 KB Output isn't correct

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1756 ms 12764 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 810 ms 5696 KB Output is correct - 41661 call(s) of encode_bit()
4 Correct 1 ms 4604 KB Output is correct - 116 call(s) of encode_bit()
5 Incorrect 1011 ms 6584 KB Output isn't correct
6 Incorrect 1170 ms 6776 KB Output isn't correct
7 Incorrect 1815 ms 7368 KB Output isn't correct
8 Correct 1186 ms 5452 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 797 ms 5476 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 823 ms 5484 KB Output is correct - 21049 call(s) of encode_bit()
11 Incorrect 872 ms 5980 KB Output isn't correct
12 Correct 938 ms 5272 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 1607 ms 6920 KB Output isn't correct
14 Correct 930 ms 5472 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 964 ms 5548 KB Output is correct - 26210 call(s) of encode_bit()
16 Correct 1037 ms 6624 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 1070 ms 6464 KB Output isn't correct
18 Correct 1190 ms 6920 KB Output is correct - 46921 call(s) of encode_bit()
19 Incorrect 1326 ms 6536 KB Output isn't correct
20 Incorrect 1216 ms 7424 KB Output isn't correct
21 Incorrect 1339 ms 7812 KB Output isn't correct
22 Incorrect 1841 ms 7052 KB Output isn't correct
23 Incorrect 1420 ms 7948 KB Output isn't correct

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1756 ms 12764 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 810 ms 5696 KB Output is correct - 41661 call(s) of encode_bit()
4 Correct 1 ms 4604 KB Output is correct - 116 call(s) of encode_bit()
5 Incorrect 1011 ms 6584 KB Output isn't correct
6 Incorrect 1170 ms 6776 KB Output isn't correct
7 Incorrect 1815 ms 7368 KB Output isn't correct
8 Correct 1186 ms 5452 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 797 ms 5476 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 823 ms 5484 KB Output is correct - 21049 call(s) of encode_bit()
11 Incorrect 872 ms 5980 KB Output isn't correct
12 Correct 938 ms 5272 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 1607 ms 6920 KB Output isn't correct
14 Correct 930 ms 5472 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 964 ms 5548 KB Output is correct - 26210 call(s) of encode_bit()
16 Correct 1037 ms 6624 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 1070 ms 6464 KB Output isn't correct
18 Correct 1190 ms 6920 KB Output is correct - 46921 call(s) of encode_bit()
19 Incorrect 1326 ms 6536 KB Output isn't correct
20 Incorrect 1216 ms 7424 KB Output isn't correct
21 Incorrect 1339 ms 7812 KB Output isn't correct
22 Incorrect 1841 ms 7052 KB Output isn't correct
23 Incorrect 1420 ms 7948 KB Output isn't correct

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1756 ms 12764 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 810 ms 5696 KB Output is correct - 41661 call(s) of encode_bit()
4 Correct 1 ms 4604 KB Output is correct - 116 call(s) of encode_bit()
5 Incorrect 1011 ms 6584 KB Output isn't correct
6 Incorrect 1170 ms 6776 KB Output isn't correct
7 Incorrect 1815 ms 7368 KB Output isn't correct
8 Correct 1186 ms 5452 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 797 ms 5476 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 823 ms 5484 KB Output is correct - 21049 call(s) of encode_bit()
11 Incorrect 872 ms 5980 KB Output isn't correct
12 Correct 938 ms 5272 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 1607 ms 6920 KB Output isn't correct
14 Correct 930 ms 5472 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 964 ms 5548 KB Output is correct - 26210 call(s) of encode_bit()
16 Correct 1037 ms 6624 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 1070 ms 6464 KB Output isn't correct
18 Correct 1190 ms 6920 KB Output is correct - 46921 call(s) of encode_bit()
19 Incorrect 1326 ms 6536 KB Output isn't correct
20 Incorrect 1216 ms 7424 KB Output isn't correct
21 Incorrect 1339 ms 7812 KB Output isn't correct
22 Incorrect 1841 ms 7052 KB Output isn't correct
23 Incorrect 1420 ms 7948 KB Output isn't correct