oj.uz

Submission #1111253

# Submission time Handle Problem Language Result Execution time Memory
1111253 2024-11-11T21:11:58 Z StefanSebez Room Temperature (JOI24_ho_t1) C++14
20 / 100
 1 ms 592 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int inf=1e9;
int n,T;
ll Plus(ll a,ll b){while(a<0)a+=T;a%=T;while(b<0)b+=T;b%=T;return (a+b)%T;}
int Dist(int x,int y){
	while(x<0)x+=T;x%=T;
	while(y<0)y+=T;y%=T;
	return min(abs(x-y),T-abs(x-y));
}
int main(){
    scanf("%i%i",&n,&T);
    int a[2*n+10];for(int i=1;i<=n;i++) scanf("%i",&a[i]),a[i]%=T;
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) a[i+n]=a[i];
    //for(int i=1;i<=n;i++) printf("%i ",a[i]);printf("\n");
    int res=0;
    /*for(int i=1,j=2;i<=n;i++){
		while(j<2*n&&Dist(a[i],a[j])<=Dist(a[i],a[j+1]))j++;
		//printf("%i: %i\n",a[i],a[j]);
		res=max(res,(Dist(a[i],a[j])+1)/2);
    }*/
    pair<int,int>b[n+10];
    ll l=0,r=(T-1)/2;
    while(l<=r){
		ll mid=l+r>>1;
		vector<pair<int,int>>ev;
		for(int i=1;i<=n;i++){
			int l=Plus(a[i],-mid),r=Plus(a[i],mid);
			//printf("%i %lld: %i %i\n",a[i],mid,l,r);
			if(l<=r) ev.pb({l,1}),ev.pb({r+1,-1});
			else{
				ev.pb({0,1}),ev.pb({r+1,-1});
				ev.pb({l,1}),ev.pb({T,-1});
			}
		}
		sort(ev.begin(),ev.end());
		int sum=0;bool bul=false;
		for(auto i:ev){
			sum+=i.se;
			if(sum==n) bul=true;
		}
		if(bul){res=mid;r=mid-1;}
		else l=mid+1;
    }
    printf("%i\n",res);
    return 0;
}

Compilation message

Main.cpp: In function 'int Dist(int, int)':
Main.cpp:12:2: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   12 |  while(x<0)x+=T;x%=T;
      |  ^~~~~
Main.cpp:12:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   12 |  while(x<0)x+=T;x%=T;
      |                 ^
Main.cpp:13:2: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   13 |  while(y<0)y+=T;y%=T;
      |  ^~~~~
Main.cpp:13:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   13 |  while(y<0)y+=T;y%=T;
      |                 ^
Main.cpp: In function 'int main()':
Main.cpp:31:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |   ll mid=l+r>>1;
      |          ~^~
Main.cpp:28:18: warning: unused variable 'b' [-Wunused-variable]
   28 |     pair<int,int>b[n+10];
      |                  ^
Main.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%i%i",&n,&T);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:18:46: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     int a[2*n+10];for(int i=1;i<=n;i++) scanf("%i",&a[i]),a[i]%=T;
      |                                         ~~~~~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 508 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 564 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 336 KB Output is correct

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Incorrect 1 ms 592 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Incorrect 1 ms 592 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 508 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 564 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 592 KB Output is correct
16 Correct 1 ms 592 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 592 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 592 KB Output is correct
21 Incorrect 1 ms 592 KB Output isn't correct
22 Halted 0 ms 0 KB -