제출 #60108

#제출 시각아이디문제언어결과실행 시간메모리
60108dukati8말 (IOI15_horses)C++14
17 / 100
1551 ms12244 KiB
#include "horses.h" #include <bits/stdc++.h> #define rep(i,a,b) for(int i=a; i<int(b); i++) using namespace std; int n; long long x[500000],y[500000]; long long m=1000000000+7; pair<long long,long long> invgcd(long long a, long long b) { //Returns x and y such that ax+by=1 if (a==1 && b==0) return make_pair(1,0); long long c=a%b; long long d=a/b; pair<long long, long long > ans = invgcd(b,c); return make_pair(ans.second,ans.first-ans.second*d); } long long inverse2(long long a) { pair<long long, long long > ans = invgcd(m,a); return ans.second+m; } long long powsmart(long long a,long long b) { if (b==1) return a; long long x=powsmart(a,b/2); x=(x*x)%m; if (b%2==0) { return x; } else return (a*x)%m; } long long inverse( long long a) { //calculate a**(m-2) return powsmart(a%m,m-2); } int init(int N, int X[], int Y[]) { n=N; rep (i,0,n) { x[i]=X[i]; y[i]=Y[i]; } long long product=1; rep (i,0,n) { product*=x[i]; product%=m; } long long hi=y[n-1]; long long divide=1; for (int i = n-2; i>=0; i--) { hi*=x[i+1]; hi=max(hi,y[i]); divide*=x[i+1]; if (hi>=1000000000) break; } long long ans=hi*product; ans%=m; ans*=inverse(divide); ans%=m; return ans; } int updateX(int pos, int val) { x[pos]=val; long long product=1; rep (i,0,n) { product*=x[i]; product%=m; } long long hi=y[n-1]; long long divide=1; for (int i = n-2; i>=0; i--) { hi*=x[i+1]; hi=max(hi,y[i]); divide*=x[i+1]; if (hi>=1000000000) break; } long long ans=hi*product; ans%=m; ans*=inverse(divide); ans%=m; return ans; } int updateY(int pos, int val) { y[pos]=val; long long product=1; rep (i,0,n) { product*=x[i]; product%=m; } long long hi=y[n-1]; long long divide=1; for (int i = n-2; i>=0; i--) { hi*=x[i+1]; hi=max(hi,y[i]); divide*=x[i+1]; if (hi>=1000000000) break; } long long ans=hi*product; ans%=m; ans*=inverse(divide); ans%=m; return ans; }

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In function 'long long int powsmart(long long int, long long int)':
horses.cpp:24:13: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   long long x=powsmart(a,b/2);
             ^
horses.cpp:7:11: note: shadowed declaration is here
 long long x[500000],y[500000];
           ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:60:9: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return ans;
         ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:84:9: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return ans;
         ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:106:9: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return ans;
         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...